faiyaz26's blog

Need Help on SQRTN Segment Data Structure!!
By faiyaz26, 12 years ago, In English

I am trying to solve this problem UVA 12477 ( PDF ).

I am thinking about the solution with SQRTN Segment which is described here — http://e-maxx.ru/algo/sqrt_decomposition

I know how to add elements in SQRTN Segment Data Structure. But how to use this data structure when we need to change all the elements for a certain segment to a value X ? Example: Update called 0 in the problem UVA 12477.

Can anyone help me with some good explanations for this array [1 index based ] ?

1 2 3 4 5 6 7

updates: 1. change the values of 3 to 6 to 10. 2. change the value of 1 to 7 to 100. 3. give the sum for 4 to 7.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The same technique as for segment tree: you store additional variable for each SQRT block named toset. It stores value to which elements of block should be changed. When you access separate elements of block, you just update the whole block in and recalculate sum of its elements. I've changed your example a bit (I split different blocks with | and write toset above the array):

 null    null   null
1 2 3 | 4 5 6 | 7 8
  1. Change the values from 3 to 6 to 10. We need some elements of block 1 and the whole block 2. So, we can set toset[2] to 10 instead of running down all its elements:
 null     10     null
1 2 10 | 4 5 6 | 7 8
  1. Change the values from 6 to 8 to 100. We need to access only a part of block 2, so it's neccessary to update its elements with value of toset[2]. Block 3 is required entirely, so we use toset[3].
 null     null      null
1 2 10 | 10 10 10 | 7 8 

 null     null       100
1 2 10 | 10 10 100 | 7 8
  1. Get the sum of elements from 2 to 8. We do it in the following way: calculate elements 2 and 3 separately (as we don't need the whole block 1), add sum of block 2 and then we add 100*2, because we know that all elements of block 3 should be 100 and it contains 2 elements.
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the reply. But after putting the value x to toset [i]. how you are upgrading the individual elements? after 1st step, you have set toset[2] to 10. then after that, you changed all the values of individual items in that block in next step. isnt it? if that process occurs, then it will become slow, isnt it? it will become O(n) , isnt it? am i wrong ?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I upgrade inividuals only when I need to access part of a block. When I access the whole block, I can use toset itself.

      On each step partly accessed blocks has summary length less than , so it does not affect time complexity

      → Reply