2D Segment/Quad Tree Explanation with C++

Question

P.S. This is may be not a duplicate. I searched SO and make sure that I didn't get what I am seeking for.

I am an ACM problem solver and Recently I've learnt Segment Tree for linear array and Segment Tree with lazy propagation. But I am encountering some problems which need 2D segments tree (which is referred as Quad tree in somewhere). But I can't find any good tutorials on it. I searched SO and found a link http://e-maxx.ru/algo/segment_tree which is a tutorial in Russian language.

I need some good explanation with source code(preferably in C++) on 2D segment Tree. It is to be noted that, I know typical segment tree pretty well.

Solution

Well, as you said and I hope you know segment tree (aka statistic tree) well enough. I am giving some intuition behind multidimensional segment tree.

---

Suppose you’re given a two dimensional N * N (for a pretty large N, large enough to be not handled by brute-force) grid of integer value and you’re asked to perform operations – find the minimum/maximum value or calculate the sum of all items of a particular portion of the grid, update any of the grid index value etc. It seems, the problem is no different than typical segment tree problem unlike the dimension of data container. What can be a choice here is building a 2D Segment Tree.

The idea of 2D segment tree is nothing but the Quad Tree - A tree data structure in which each external node has exactly four children. Quad trees are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular or may have arbitrary shapes. The data structure was named a quadtree by Raphael Frinkel and J. L. Bentley in 1974. A similar partitioning is also known as Q-tree.

The root of the tree contains the full segments through [ (0, 0), (N - 1, N - 1) ]. And for each segment [ (a1, b1), (a2, b2) ], we split them into [ (a1, b1), ( (a1 + a2) / 2, (b1 + b2) / 2 ) ) ], [ ( (a1 + a2) / 2 + 1, b1 ), ( a2, (b1 + b2) / 2 ) ], [ ( a1, (b1 + b2) / 2 + 1 ), ( (a1 + a2) / 2, b2 ) ] and [ ( (a1 + a2) / 2 + 1, (b1 + b2) / 2 + 1 ), ( a2, b2 ) ] until a1 = b1 and a2 = b2. The cost of building a segment tree is O(nlogn) and with segment tree ready answering an RMQ (Range maximum/minimum query) can be done in O(logn).

Suppose, you are given a grid with N = 4. Then the corresponding tree will be -

As you see, the 4 * 4 array [ (0, 0), (3, 3) ] is segmented into 4 sub-arrays – [ (0, 0), (1, 1) ], [ (2, 0), (3, 1) ], [ (2, 0), (1, 3) ] and [ (2, 2), (3, 3) ]. And further, each four chunks are segmented into four smaller units; For example segment [ (2, 2), (3, 3) ] will be [ (2, 2), (2, 2) ], [ (3, 2), (3, 2) ], [ (2, 3), (2, 3) ] and [ (3, 3), (3, 3) ]. These segments are the smallest unit so no more further division.

Implementation

The coding part is very similar to segment tree unlike the segmentation part. The code given here is programming contest friendly (no pointer, memory allocation/deallocation stuff and OOP structure) and I've used this snippet many times in contests.

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 501
#define INF (1 << 30)
int P[Max][Max]; // container for 2D grid
 
/* 2D Segment Tree node */
struct Point {
    int x, y, mx;
    Point() {}
    Point(int x, int y, int mx) : x(x), y(y), mx(mx) {}
 
    bool operator < (const Point& other) const {
        return mx < other.mx;
    }
};
 
struct Segtree2d {

    // I didn't calculate the exact size needed in terms of 2D container size.
    // If anyone, please edit the answer.
    // It's just a safe size to store nodes for MAX * MAX 2D grids which won't cause stack overflow :)
    Point T[500000]; // TODO: calculate the accurate space needed
    
    int n, m;
 
    // initialize and construct segment tree
    void init(int n, int m) {
        this -> n = n;
        this -> m = m;
        build(1, 1, 1, n, m);
    }
 
    // build a 2D segment tree from data [ (a1, b1), (a2, b2) ]
    // Time: O(n logn)
    Point build(int node, int a1, int b1, int a2, int b2) {
        // out of range
        if (a1 > a2 or b1 > b2)
            return def();
 
        // if it is only a single index, assign value to node
        if (a1 == a2 and b1 == b2)
            return T[node] = Point(a1, b1, P[a1][b1]);
 
        // split the tree into four segments
        T[node] = def();
        T[node] = maxNode(T[node], build(4 * node - 2, a1, b1, (a1 + a2) / 2, (b1 + b2) / 2 ) );
        T[node] = maxNode(T[node], build(4 * node - 1, (a1 + a2) / 2 + 1, b1, a2, (b1 + b2) / 2 ));
        T[node] = maxNode(T[node], build(4 * node + 0, a1, (b1 + b2) / 2 + 1, (a1 + a2) / 2, b2) );
        T[node] = maxNode(T[node], build(4 * node + 1, (a1 + a2) / 2 + 1, (b1 + b2) / 2 + 1, a2, b2) );
        return T[node];
    }
 
    // helper function for query(int, int, int, int);
    Point query(int node, int a1, int b1, int a2, int b2, int x1, int y1, int x2, int y2) {
        // if we out of range, return dummy
        if (x1 > a2 or y1 > b2 or x2 < a1 or y2 < b1 or a1 > a2 or b1 > b2)
            return def();
 
        // if it is within range, return the node
        if (x1 <= a1 and y1 <= b1 and a2 <= x2 and b2 <= y2)
            return T[node];
 
        // split into four segments
        Point mx = def();
        mx = maxNode(mx, query(4 * node - 2, a1, b1, (a1 + a2) / 2, (b1 + b2) / 2, x1, y1, x2, y2) );
        mx = maxNode(mx, query(4 * node - 1, (a1 + a2) / 2 + 1, b1, a2, (b1 + b2) / 2, x1, y1, x2, y2) );
        mx = maxNode(mx, query(4 * node + 0, a1, (b1 + b2) / 2 + 1, (a1 + a2) / 2, b2, x1, y1, x2, y2) );
        mx = maxNode(mx, query(4 * node + 1, (a1 + a2) / 2 + 1, (b1 + b2) / 2 + 1, a2, b2, x1, y1, x2, y2));
 
        // return the maximum value
        return mx;
    }
 
    // query from range [ (x1, y1), (x2, y2) ]
    // Time: O(logn)
    Point query(int x1, int y1, int x2, int y2) {
        return query(1, 1, 1, n, m, x1, y1, x2, y2);
    }
 
    // helper function for update(int, int, int);
    Point update(int node, int a1, int b1, int a2, int b2, int x, int y, int value) {
        if (a1 > a2 or b1 > b2)
            return def();
 
        if (x > a2 or y > b2 or x < a1 or y < b1)
            return T[node];
 
        if (x == a1 and y == b1 and x == a2 and y == b2)
            return T[node] = Point(x, y, value);
 
        Point mx = def();
        mx = maxNode(mx, update(4 * node - 2, a1, b1, (a1 + a2) / 2, (b1 + b2) / 2, x, y, value) );
        mx = maxNode(mx, update(4 * node - 1, (a1 + a2) / 2 + 1, b1, a2, (b1 + b2) / 2, x, y, value));
        mx = maxNode(mx, update(4 * node + 0, a1, (b1 + b2) / 2 + 1, (a1 + a2) / 2, b2, x, y, value));
        mx = maxNode(mx, update(4 * node + 1, (a1 + a2) / 2 + 1, (b1 + b2) / 2 + 1, a2, b2, x, y, value) );
        return T[node] = mx;
    }
 
    // update the value of (x, y) index to 'value'
    // Time: O(logn)
    Point update(int x, int y, int value) {
        return update(1, 1, 1, n, m, x, y, value);
    }
 
    // utility functions; these functions are virtual because they will be overridden in child class
    virtual Point maxNode(Point a, Point b) {
        return max(a, b);
    }
 
    // dummy node
    virtual Point def() {
        return Point(0, 0, -INF);
    }
};
 
/* 2D Segment Tree for range minimum query; a override of Segtree2d class */
struct Segtree2dMin : Segtree2d {
    // overload maxNode() function to return minimum value
    Point maxNode(Point a, Point b) {
        return min(a, b);
    }
 
    Point def() {
        return Point(0, 0, INF);
    }
};
 
// initialize class objects
Segtree2d Tmax;
Segtree2dMin Tmin;
 
 
// Driver program.
int main(void) {
    int n, m;
    // input
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &P[i][j]);
 
    // initialize
    Tmax.init(n, m);
    Tmin.init(n, m);
 
    // query
    int x1, y1, x2, y2;
    scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
 
    Tmax.query(x1, y1, x2, y2).mx;
    Tmin.query(x1, y1, x2, y2).mx;
 
    // update
    int x, y, v;
    scanf("%d %d %d", &x, &y, &v);
    Tmax.update(x, y, v);
    Tmin.update(x, y, v);
 
    return 0;
}

3D Segmentation

It is not impossible that you are given a 3D grid and asked to perform similar operations like 2D segment tree. In this case, We can construct a 3D Segment tree just like we did for 2D grid.

We will split the grid into 8 smaller segments and recursively do subdividing until the smallest unit appears. The below picture show this segmentation idea.

For, 1D segment tree, We divide the array into 2 (2^1) segments and that yields a log2(n) complexity for particular operations. Again for 2D segment tree, We split the 2D grid in every step into 4 (2^2) segments which ensure every operations with log2(n) cost. So in a similar fashion, We expand this 3D tree by subdividing the grid into 8 (2^3) segments.

P.S.: The 3D segment tree is my own imagination; I don't know if there is anything like that. May be there is a better way for both 2D and 3D segment tree out there, But I think these code suffice for programming contests as I have used these many times.

---

Edit:

The idea of 3D segmentation is nothing but the Octree - a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees.

Octrees are often used in 3D graphics and 3D game engines. It has a lot of other applications like Spatial indexing, Nearest neighbor search, Efficient collision detection in three dimensions and so many.

Hope it helps!

Comments

[robbrit]

Can you show us some examples of what you've tried so far?

[robbrit]

Also, a quick Google search for "quadtree" gives me this: gamedevelopment.tutsplus.com/tutorials/…

[tmyklebu]

Quadtrees are different. Look up "range trees." A 2D range tree is basically just a tree (on x) of segment trees (on y).

[Sazzad Hissain Khan]

See the implementation here github.com/hissain/advance-data-structures-algorithms/blob/…

[Gene]

This isn't right. 3D segmentation has lots of has common uses. Octrees are used to represent solids in many graphics applications. Given a collection of circles in the plane and one distinguished circle (P1,r1), find the circle in the collection (P2,r2) minimizing dist(P1,P2)-r1-r2.

[Kaidul]

@Gene Thanks. I didn't know about Octree. Thanks for this information, I am editing my answer

[lavee_singh]

Can I get non-recursive implement of query function in 2-d segment tree? This recursive function is running very slow on large 2-d arrays.

[lavee_singh]

What is expected time complexity for this query function?

[Kaidul]

@lavee_singh Query and update both are logarithmic. Did you fix your problem?

[ffao]

Query in a quad-tree is O(n), not O (log n) or O (log^2 n). Consider for instance a query in a 1xN rectangle, it will be split into N 1x1 rectangles.

[Turkhan Badalov]

I think [ (2, 0), (1, 3) ] should be [ (0, 2), (1, 3) ]. Third child (counting from the left) of root node.

[Sazzad Hissain Khan]

quad tree is not a 2d segment tree. update in quad tree is O(N) where in 2d segment tree O(log^2N)