zeref_dragoneel's blog

2-D segment tree with less memory
By zeref_dragoneel, history, 8 years ago, In English

Hi,

I am trying to implement a 2-D segment tree, seg with N = 100000... The catch is that I only need to get the query answer for Q(100000) nodes say query(i,j) : denoting the value in seg[i][j]... but i need to online (lazily) update the seg tree, seg[lx...rx][ly...ry].

Can anyone help me with this problem?

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zeref_dragoneel (previous revision, new revision, compare).

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

What is the problem with using a dynamic 2D segment tree?

Another way which is much easier and faster is using 2D compressed Fenwick tree but it will be offline.

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

    http://www.spoj.com/problems/XXXXXXXX/

    Did not get to any solution other than dynamic 2D segment tree with range updates.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it +9 Vote: I do not like it

      Well in this problem you don't need an online solution. As I said you can use 2D compressed Fenwick tree. You also can replace the inner dynamic segment tree in your solution with a compressed Fenwick or Treap. In such a way you could make the solution faster and make it use less memory. If you didn't get what I meant by compressed Fenwick, here is an implementation. If you didn't get what I meant by "replacing the inner segment tree" you can take a look at my solution to this problem (solution). I used a similar approach. It won't be hard to figure out how to reapply the same approach to the problem you've linked.

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

        Can you please elaborate on "given L, R, find the sum of a[i] for L ≤ i ≤ R such that left[i] < L. This can be done with range query in any 2D data structure."?

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

          On one dimension you have the indexes in the array and on the other one you also have the indexes in the array. Then the query becomes:

          Find sum in sub-rectangle with upper left point (L, 0) and lower right point (R, L). And when we do update we update point (i, left[i]) with value a[i].

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

            Just so that I understood it correctly, is this similar to a segment tree where each node is a treap so node (l,r) gives the treap for present indices in [0, r].

            except you are having a compressed fenwick tree instead of a treap.

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

              Exactly. That's why I mentioned that it also can be done with treap, but unfortunately I think it will not be fast enough.

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

                Thanks a lot. You helped me a lot understanding a new datastructure. :)

                → Reply