I'm sorry that I'm a Chinese and most of the English name of algorithm I don't know. So, I use google translation to translate it.

Have you ever seen the following questions?

Calculate the median of a range, and you must finish online (means you need to calculate real question by using last answer). What would you do? If the problem is not online, we can easily use persistent segment tree to solve it. And now it is online, maybe you think you can solve it by using AVL.

Now, I will show you another way to solve this question. Divide the sequence into n blocks, each blocks' size is sqrt(n). For each block, we set a segment tree that contain the value of this block.

For a question of asking [l,r], we find the blocks that the whole block of it in the range. And we use segment tree merge to merge them. And for the number that is not contained by the complete block, we insert them into the segment tree.

And we get a segment tree that contain the value of the range. And we can use segment tree binary search to solve this problem.

There is a sample: We set a array of [1,1,4,2,1,3,1,4,3], and the picture below is the block number and segment trees of the array.

If we want to ask range [2,8], we will do this below:

And we can solve something on the new segment tree.

For the time limit. We set the numbers in the array is lower than m, there are n numbers in the array. Because of the size of the block is sqrt(n) and numbers of blocks are sqrt(n), so we mostly do segment tree merge for sqrt(n) times, and mostly insert the numbers into the segment tree for 2*sqrt(n) times. And then, the time of the segment tree merge is log2(m), insert the numbers are log2(m) too. So, this algorithm's time is O(n*m*sqrt(n)*log2(m)), We can solve it in 1 seconds when n is lower than 2e5 and m is small.

But there is always a question, memory. Because we can't modify the value of the segment tree in the blocks. So we need to merge the segment tree in the blocks to the new segment tree. If we create a new segment tree for every query, the memory will not ok. So we only use one segment tree, and after every query, we clear it.

A possible code:

int l,r;
l=read(),r=read();
for(int i=l;i<=min(belong[l]*block,r);i++)
{
	update(root[nowroot],1,len,Ar[i],1);
}
if(belong[l]!=belong[r])
{
	for(int i=(belong[r]-1)*block+1;i<=r;i++)
	{
		update(root[nowroot],1,len,Ar[i],1);
	}
}
for(int i=belong[l]+1;i<=belong[r]-1;i++)
{
	merge(root[nowroot],root[i],1,len);
}

int ans=query(root[newroot]);
printf("%d\n",ans);
clear(newroot); 

In this code, block is sqrt(n), query is a function of answering the problems, update is the function of inserting numbers, merge is the function of segment tree merge.

Do you think it's useless? Yes, by now, all it can finish, we can use AVL to solve it, and it needs a longer time. But I don't know what other problems this algorithm can solve. At least, we only need to learn one algorithm, congratulation! And I think that many people who issue the problems of data structure, they will set limit of n<=1e5 and not for 1e6!

My level is limited, please give me more advice, thank you very much! :)

SOMTHING NEW

My classmate pzq_alex give me a useful remind, and I just discover this algorithm also can modify one position's value! If we want to change the value of a one position, we can modify the block's segment tree by deleting the position's original value, and adding the new value.

tfg mention that each query is nlogn, and I think about it. I discover that each query is actually sqrt(n)*m*logm. That is, when m is very small, like lower than 100 or 10, we can still use this algorithm. Because m is the max value of the array.