### orchidmajumder's blog

By orchidmajumder, 8 years ago,

Hi,I'm trying to solve this problem.It asks for point update and range query where the query is sum of distinct numbers in a given range.

Is this type of problem solvable by normal segment tree or do we need any kind of persistent data structure to do this?? I don't have much idea about persistent data structures.

Any help will be appreciated very much :)

• +14

 » 8 years ago, # | ← Rev. 2 →   0 Sorry, wrong.
 » 8 years ago, # |   0 There was theme about similar problem. But I have no idea how to adopt this algorithm to solve problem with update queries.
•  » » 8 years ago, # ^ |   0 Ya I googled it and got the DQUERY link from codeforces.But with point update,this problem looks very tough.
 » 8 years ago, # | ← Rev. 3 →   0 Wrong :)
 » 8 years ago, # | ← Rev. 5 →   +20 Old idea:How to count distinct numbers in a range with update query?For each position store next position with same value, and for each range query you have to calculate how many this stored positions have value > right border.Example:values = [1, 2, 3, 1, 2, 1, 3]nextposes = [4, 5, 7, 6, inf, inf, inf]query = [2, 6]nextposes = [5, 6, 7, inf, inf], 3 of them > 6, so answer is 3.Ok, you can do this operation with 2D tree in O(lg(n)2)).You can update numbers in O(lg(n)2)) too with same trees. Update operation simple and boring: you have to find previous&next elements with old value, update tree, after that find previous&next element with new value, and update tree after.You can find this previous&next elements, if you will store positions for each value in: map < int, set < int >  >  and use lower_bound on set.Only difference between this task and yours: your tree should return sum of values instead of count. If you implement 2D tree with SegTree+Treap, you can easily maintain this sum in Treap.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +4 Hii yarrr Thanks a ton.You really explained the approach very clearly.Now,can you help me a bit on the implementation part?I have implemented treap for solving ORDERSET in spoj.So I know basic split merge and find operations of treap.And I know seg tree operations.Now can you help me in implementing this 2D tree by combining treap and seg tree?Or can you give me some reference from where I can learn this??Thanks a lot again for sparing your time to answer my question!! :)
•  » » 5 years ago, # ^ |   0 what would be the space complexity for using 2d segment tree.
 » 8 years ago, # |   0 Another O(log(n)2)-per-query solution (Sorry for my bad English).Maintain matrix B = (bi, j), where bi, j — answer to query Q i j. At first, the array and the matrix are zero. Init array using U i ai.Processing U x y:1) Set ax to zero: find left and right neighbor containing ax — l and r. This query only affects such bi, j, that l < i ≤ x ≤ j < r. They form a rectangle in matrix B, so just substract ax of this rectangle.2) Set ax to y: similar to 1)2D BIT can do it, but I'm not sure it passes ML.
•  » » 8 years ago, # ^ |   0 Hiii NuM.thanks a lot.I have got the idea.Can you help me a bit on the implementation part?
•  » » » 8 years ago, # ^ |   0
•  » » » » 8 years ago, # ^ |   0 Hii NuM , thanks a lottt..I'm going to see this and try to learn the implementation just after this Div2 contest ends.thanks again!!! :)
 » 8 years ago, # | ← Rev. 2 →   0 There is one more solution in sqrt(Q + N) * (Q + N), but it is also not easy to implement. K = 400; // ~ sqrt(N + Q) for (int time = 0; time < Q; time+= K) { // there we process only queries with Time in range [time, time + K) for (int L = 0; L < N; L += K) { for (int R = 0; R < N; R += K) { //iterate over queries with Left in range[L, L + K) and Right in [R, R + K) // update structure on 'U' queries and answer for 'Q' queries // each query can be answered in O(K) // do not forget to revert structures also in O(K) after each query processing } } // add all queries with Time in range [time, time + K) } 
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 Hii goo.gl_SsAhv thanksss..can you explain What is the significance of the 'time' thing here??
•  » » » 8 years ago, # ^ |   0 it's query number in order of appearance.
•  » » » » 8 years ago, # ^ |   0 ok thank youu :) Will try to understand this approach too :)
•  » » » » » 8 years ago, # ^ |   0 TL code.
•  » » » » » » 8 years ago, # ^ |   0 Hi goo.gl_SsAhv thanks a lot.I'm seeing urs and NuM's approach right now.Thanks again.
•  » » » » » » » 8 years ago, # ^ | ← Rev. 2 →   0 I was wrong. it's N^2. cycle after if (R >= L) { (line 186) kills everything.
•  » » » » » » » » 8 years ago, # ^ |   0 okay..