mbrc's blog

2D Segment Tree implementation
By mbrc, 10 years ago, In English

I am trying to learn 2D Segment trees, and I'm having problems implementing it. Especially when there are 2 points with same y-coordinate. Actually, the approach is to make a segment tree on the x-coordinates, and for the node with x-range [x1,x2] keep a segment tree with all y such that there exists a point (X,y) with x1<=X<=x2. Now suppose we have to update points and find maximums in a rectangle. So if I have to update point (X,Y), I go to the leaf with range [X,X], update the Y in its segment tree. But if I then come up to the parent, and try to update Y in its seg tree too, then I won't make any difference between two different points in that range with same y-coordinate Y. Please tell me if I'm incorrect, and correct me. And please provide me with a clean implementation of 2D segment trees, if you can.

If you want a clean formulation, here it is:

Given N (N<10^5) points each with an associated value, and Q queries (Q<10^5), each either a query or an update. The update operation gives you x,y,k and asks you to update the value at point (x,y) to k. The query operation gives you x1,y1,x2,y2 and asks you for the maximum in the rectangle (x1,y1)-(x2,y2). The update points are among the initially given points.

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

»
10 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Yep, you don't make any difference between points with the same Y in each node of the outer tree, because you don't have to. If you ask some inner tree something, then it's clear that L ≤ l ≤ r ≤ R, where [L, R] is the query and [l, r] is the X-segment that the inner tree is responsible for.

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

    Suppose you have two points (x1,y) and (x2,y). Let the value at point (X,Y) be denoted by V[X,Y]. Let V[x1,y] > V[x2,y] initially. So in the segment tree for the node with range [x1,x2] (assume that it exists), for the y-coordinate you have stored V[x1,y]. But now you update V[x1,y] so that V[x1,y] < V[x2,y]. Then how will you update y-coordinate in this node ([x1,x2] in outer segtree)? You hadn't kept track of V[x2,y] , but now its the maximum !

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

      Oh, I see, I'm sorry. There's a problem with formal definition of what the inner tree should do. In fact, it should be able to store several values for each Y. It can be achieved by storing multiset or something similar in each leaf node and then considering its value as maximum of elements in the multiset. It's still lograthmic time.

      Does that make sence?

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

        Yes. :D Will ask you again, if I face problems.

        → Reply
»
10 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Let us start with an example. Suppose both coordinates are from 0 to 3. Then, if you add a point (1, 2), you add 1 point to the counts in the following vertices:

([1, 1], [2, 2]), ([0, 1], [2, 2]), ([0, 3], [2, 2]),
([1, 1], [2, 3]), ([0, 1], [2, 3]), ([0, 3], [2, 3]),
([1, 1], [0, 3]), ([0, 1], [0, 3]), ([0, 3], [0, 3]).

As you can see, each vertex has two coordinates: the binary segments it covers by x and by y.

A simple operation on a two-dimensional segment tree is usually along the lines of:

for (x-segment)
  for (y-segment)
    visit vertex (x-segment, y-segment)

Or, if you need the recursive version, you can define two functions. The x-recursion (x-segment) descends by x-segment and always calls the y-recursion from the top. The y-recursion (x-segment, y-segment) keeps x-segment constant, descends by y-segment and visits the actual vertex (x-segment, y-segment).

See e-maxx.ru for some example code (and an explanation that may be Google-translatable).

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

    Tried to translate e-maxx.ru, Google Translate didn't quite work. Thanks for explaining with an example. I needed an example. :D

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

      I had the same problem, just use the integrated translator on google chrome

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

https://stackoverflow.com/questions/25121878/2d-segment-quad-tree-explanation-with-c/25122078#25122078 this link will definitely help !! :)

→ Reply