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.
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.
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 !
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
multisetor something similar in each leaf node and then considering its value as maximum of elements in themultiset. It's still lograthmic time.Does that make sence?
Yes. :D Will ask you again, if I face problems.
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:
As you can see, each vertex has two coordinates: the binary segments it covers by
xand byy.A simple operation on a two-dimensional segment tree is usually along the lines of:
Or, if you need the recursive version, you can define two functions. The
x-recursion (x-segment)descends byx-segmentand always calls they-recursionfrom the top. They-recursion (x-segment, y-segment)keepsx-segmentconstant, descends byy-segmentand visits the actual vertex(x-segment, y-segment).See e-maxx.ru for some example code (and an explanation that may be Google-translatable).
Tried to translate e-maxx.ru, Google Translate didn't quite work. Thanks for explaining with an example. I needed an example. :D
I had the same problem, just use the integrated translator on google chrome
https://stackoverflow.com/questions/25121878/2d-segment-quad-tree-explanation-with-c/25122078#25122078 this link will definitely help !! :)
This will not work for sure, 2-d segment tree != quad-tree