I am trying to solve a seemingly standard segment tree problem. The problem can be found here . I came up with a solution to the problem using square root decomposition. Though the complexity of the solution is enough to pass the time limit but the tutorial describes the solution using segment trees. It talks about constructing 3 segment trees.
- First segment tree stores at any given node how many numbers are divisible by 3 in the corresponding range.
For e.g.
Consider an array of 4 integers [0 0 0 0]
1. Increment every number in range 0-3 by 1
2. Increment every number in range 0-1 by 1
3. Increment every number in range 0-2 by 1
At this stage node corresponding to range 0-3 should store 0 because addition of 1 to the whole
range leaves no number divisible by 3.
- Second segment tree stores how many numbers leave a remainder 1 on division by 3.
In the above example, node corresponding to range 0-3 would store 4. - Stores the quantity added to a particular range only.
In the above example, node corresponding to range 0-3 would store 1.
I couldn't understand how to update the tree1 and tree2 on increment operation?
i can't understand what is this means: "3) add[k] : What is the quantity which is added to all numbers totally inside this range and not considering additions performed on ranges which are a subrange of the range covered at node k/2".
Ranges of subranges of subranges ranges covered by bla bla not including bla bla bla. can anybody translate it into Russian or describe this in more comfortable way?
I think tutorial describes not 3 different segment trees, but one where each node stores 3 integers, and when we preform some operations we can update all the numbers. I think is is easier to store at each node k three numbers a[k][0..2] a[k][i] — quantity of numbers inside segment which have remainder equal to i.
How do we perform a range update on such a segment tree?
google lazy propagation segment tree.
code