Ohk so lets talk abt the logic to solve
Lets say arr is [3,4,4,3,4]
I want to know the ans for range[1,4]
Lets create a nxt which contains index of nxt occurence,if no occurrence after,then nxt[i]=6 lets say
So ans for range [1,4] is no.of elements greater than 4(ie r)
Reason?-> lets say 2 sane elements occur in range(1,4) ,obviously the first of them will have nxt less than r(since the next element is in the range),2nd element will have nxt greater than r.
Now question reduces to how to find no.of elements greater than r in range[l,r].
For handling updates u can simply store the indices of elements in vector.
Ie for 3 4 4 3 4
So now u can easily update(just change the prev element nxt and this element nxt accordingly )
Now coming back to og question,no.of elements greater than r,
Divide the array into sqrt blocks ,sort each block,then just binary search for r in each block to find no.of elements greater than r
2)segment tree with ordered set in each node
Lets say each node consists of ordered set of the range.So u can simply binary search and find no.of elements greater than r
,see this for ordered set:-
3)segment tree with each node having a dynamic segment tree
This is similar to the above method.One can have a dynamic segment tree in each node,where that DST[range] gives no.of elements in range.
Just in case if no update were there u could do :-
Wavelet tree ( link:- http://codeforces.com/blog/entry/52854)
I dont know if update can be done on this
5)persistent segment tree
Build a persistent segmnet tree such that seg[i:j] gives count of number of elements(values not indices) in (i,j).
So to ans (l,r) :- rthseg[r+1,inf] - (l-1)thseg[r+1,inf]
(Xthseg[i,j] denite no.of elements with values in range(i,j) and indices (1,X))
Complexity :- O(qlogn)
And last method
6)simple segment tree
See to answer (l,r) if we know no.of elements in range[1,r] and [1,l-1] greater than r,then ans is simply difference of the two
So just process the queries lyk,lets say we have queries :-
So i have to calculate (i,j) which denote no.of elements greater than j in range[1,i]
I mean we have to calculate (2,5),(5,5),(1,4),(4,4)
Now sort these values in decreasing order based on first value
Now lets say we have a segment tree where seg[range] returns no.of elements in range.
So to ans (i,j) we need to have a segment tree of first i elements and query for range[j+1,inf]
So as we process it backwards we can easily process all queries(ie first u have seg tree for first 5 elements ,so if want for 4 elements delete the 5th element)
Complexity :- O(qlogn)
Sorry if my comment is too large,i’ ve written it just in case if any1 else wanna know.
(And yeah if A[i] is large u can use cordinate compression(which is basically mapping them to small values after sorting))