How to efficiently get frequency of subranges and update its values altogether?
Almost one year later... I tried to solve it today without looking my previous code and I got ACC'ed now. (ideone link)

Reading my question now, I've implemented what I called delta and rotate in a simpler way. I will try to illustrate.

This is how the segment tree for N = 5 looks like after build():



My node struct has:

int freq[9], i, lazy;


The i variable is the position circled in red in the picture, it will hold which position of the freq array contains the frequency for note 0 (which initially is zero). The lazy flag stores pending sums for children (both left and right), blue in the picture.

Now suppose first query for [1, 2]. The query() function will find nodes [1, 1] and [2, 2] and the resulting int fquery[9] array will have values [0,2,0,0,0,0,0,0,0]. The greatest() value then is 1. Ok, this is a simple search.

Now the function chord() will update those ranges by setting lazy += 1 and i -= 1:



Note that since those are leaf nodes, the lazy property does nothing. Also note that since i was decreased, there is no need to update freq[] array. This two things were done in the pre-order traversal of the recursive chord() function.

Now we update the freq[] array of the parents using the post-order traversal of the recursive chord() function by calling update(), this update function is just a merge of left and right child nodes:



These separation of pre-order and post-order traversal of the recursive call was the main point that I didn't understand last year. I was trying to update the parents out of the recursion track, and it caused me TLE.

Now suppose second query for [0, 4]. The query() function will find node [0, 4] and the resulting int fquery[9] array will have values [0,3,2,0,0,0,0,0,0]. The greatest() value then is 1.

Now the function chord() will set lazy += 1 and i -= 1:



Since we found the desired range in the root, this time we don't have post-order traversal.

Now suppose third query for [0, 2]. The query() function will find node [0, 2]. But, we can only reach a node if there is no pending sums. So, we need to resolve the lazy = 1 flag of node [0, 4]. This is what propagate() function does:



Note: the i value of node [0, 2] is 8.

And the resulting int fquery[9] array will have values [0,0,1,2,0,0,0,0,0]. The greatest() value then is 3.

Now the function chord() will set lazy += 3 and i -= 3:



As previously, we update the freq[] array of the parents using the post-order update():



To get the output after all queries, you just need to propagate() every node, doing so the leaf nodes will have the final values. You can check the show() function.

The output for this example will be: 5 6 6 2 2. (The first test case in the URI Online Judge).



Conclusion: The solution to the problem is a standard segment tree with lazy propagation with each node containing an int freq[9] array and an additional index starter holder.