orchidmajumder's blog

Sum of distinct elements in a range
By orchidmajumder, 11 years ago, In English

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.

Problem Link

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 :)

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Sorry, wrong.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There was theme about similar problem. But I have no idea how to adopt this algorithm to solve problem with update queries.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ya I googled it and got the DQUERY link from codeforces.But with point update,this problem looks very tough.

    → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Wrong :)

→ Reply
»
11 years ago, # |
← Rev. 5   Vote: I like it +20 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    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!! :)

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what would be the space complexity for using 2d segment tree.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hiii NuM.thanks a lot.I have got the idea.Can you help me a bit on the implementation part?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      code

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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!!! :)

        → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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)
}
→ Reply