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.
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):
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 ?
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