Hi,
problem:
Given an array with N elements you have to execute two different types of querys:
1- add to the array an element with value X (anywhere).
2- answer how many elements which have value bigger than l and smaller than r.
constrains:
number of querys<=100,000
N<=100,000
l<=r<=N
X<=10^9
I think it can be done using self-balancing binary search tree (for example AVL tree),
but is there is a way easier than this data structure?
I need an ONLINE solution
I'd use treap with implicit keys.
Take a look:
http://www.codeforces.com/blog/entry/3767
It is called there 'Implicit Cartesian Tree'.
Thank you.
I will see which is easier BST or Implicit Cartesian Tree.
I think, if X ≤ 105, you may solve the problem using Segment Tree.
If X ≤ 109, you may use Dynamic Segment Tree.
Description of data structure:
At first we have only one vertex — the root
All queries are processed from up to down
When we want to use vertex, and it does not exist, we create it.
Asymptotics (X ≤ M, Q — number of queries):
Time = O(logM) per query
Memory = O(QlogM)
I will get TLE if the segment tree is unbalanced(when I create new nodes)
Ok, let describe Segment Tree more precisely:
root = [1..10^9]
if v = [L..R] then v.left = [L..M], v.right = [M+1..R], where M = (L+R)/2
Depth of such tree is exatcly
and the range that don't have any element inside it we don't create it until it have one element, right? , then we can't code the segment tree like a heap (if node index is i then its sons 2*i ,2*i+1) we have to use pointers in this case,now I got you thank you.
Actually, you can do it with STL. You can find it here
e.e 6 years ago...
Better late than never