Keep 2 kinds of queries:
1. (x,i) : The ith position is supposed to be assigned value x
2. (x,l,r): Count number of elements in [l,r] which are less than x

So obviously the queries are of the form (a[i],i) for i from 1 to n, and the range queries that we have. Now sort all the queries by x. Keep a segment tree over 1 to n. Initially, all the nodes have the value 0. Now whenever you encounter the first query, set the value at i to 1. For the second query the answer is just the number of 1's from l to r, which is a normal range sum query.

You can see pretty easily that this works.

No, I did not.

By "merge-sort-like-tree" I mean the following: suppose we have a standard segment tree over an array, but each node stores (instead of a fixed-size value) a sorted list of all values in the corresponding subtree. Here is an example for array 4 6 2 1 7 3 8 5:

[1  2  3  4  5  6  7  8] - values on positions 1-8 (node 1)
[1  2  4  6][3  5  7  8] - values on positions 1-4, 5-8 (nodes 2 and 3)
[4  6][1  2][3  7][5  8] - values on positions 1-2, 3-4, 5-6, 7-8 (nodes 4-7)
[4][6][2][1][7][3][8][5] - values on positions 1, 2, ..., 8 (nodes 8-15)

That data structure can easily calculate number of elements less than X whose positions are between L and R in — just split [L;R] into nodes and run binary search inside each node. With fractional cascading we can reduce that time into by running binary search on the top level only.

Wavelet tree does something similar: instead of looking at values

(1, 4); (2, 6); (3, 2); (4, 1); (5, 7); (6, 3); (7, 8); (8, 5)

it looks at

(4, 1); (6, 2); (2, 3); (1, 4); (7, 5); (3, 6); (8, 7); (5, 8)
similar to
(1, 4); (2, 3); (3, 6); (4, 1); (5, 8); (6, 2); (7, 5); (8, 7)

and builds something similar to the structure we had above: each node corresponds to a sub-segment of possible values and contains their sorted positions (we have no need to store the positions explicitly, we just pretend that they're here):

[1  2  3  4  5  6  7  8] - positions of values 1-8 (node 1)
[1  3  4  6][2  5  7  8] - positions of values 1-4, 5-8 (nodes 2-3)
[3  4][1  6][2  8][5  7] - positions of values 1-2, 3-4, 5-6, 7-8 (nodes 4-7)
[4][3][6][1][8][2][5][7] - positions of values 1, 2, ..., 8 (nodes 8-15)

If we can compress values, persistent segment tree is . If we can't, wavelet tree is also .

I didn't mean persistent segment tree is better than wavelet tree,and wavelet tree certainly does better in these kind of problems.I just point out that there exists an alternative way to solve these kind of problems.

What's more,if we are asked to update values and even insert new values,we can use binary search tree without rotations(In China it's called Scape-Goat Tree) and segment tree to solve the problem in O(nlog^2n) time complexity.

There is a problem of this kind which you're asked to ask queries of the k-th smallest element in a range as well as update and insert elements.

Problem Link(in Chinese)

You should read the paper :) the first question is answered in detail there. The answer for the simplest case when you have an array of N elements (in a reasonable alphabet, for example, numbers < 10^9) is O(lg(N)) per query.

For the updates, in the paper we covered some cases, like toggling, adjacent-swapping, push_back and push_front.

Have you used index compression? The numbers can be up to 10^9

I also tried the same problem and im getting WA. I implemented by myself but I compared with some other codes and seems pretty much the same. Can anyone help me? code

Thanks!