2D Segment/Quad Tree Explanation with C

segment-tree

quadtree

cplusplus

data-structures

programming-tutorial

2D Segment/Quad Tree Explanation with C

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

Data Structures

Introduction

Both 2D segment trees and quadtrees are used to answer spatial queries efficiently, but they solve the problem in different ways. A 2D segment tree is usually better when you have a fixed grid and want predictable rectangular range queries, while a quadtree is often a better fit for sparse geometric points distributed across space.

What a 2D Segment Tree Stores

A normal segment tree indexes one dimension. A 2D segment tree extends that idea so each node on one axis also stores information for the other axis.

Typical use cases include:

sum in a sub-rectangle
minimum or maximum in a rectangle
point updates on a fixed 2D grid

Conceptually, you can think of it as a tree of trees. That makes queries fast, but also makes the structure heavier in memory and code complexity.

A Small 2D Segment Tree Example

The following C++ example shows the core idea for range-sum queries on a small matrix:

cpp

1#include <iostream>
2#include <vector>
3using namespace std;
4
5class SegmentTree2D {
6public:
7    SegmentTree2D(const vector<vector<int>>& grid)
8        : rows(grid.size()), cols(grid[0].size()),
9          tree(4 * rows, vector<int>(4 * cols, 0)), data(grid) {
10        buildX(1, 0, rows - 1);
11    }
12
13    int query(int x1, int y1, int x2, int y2) {
14        return queryX(1, 0, rows - 1, x1, x2, y1, y2);
15    }
16
17private:
18    int rows, cols;
19    vector<vector<int>> tree;
20    vector<vector<int>> data;
21
22    void buildY(int vx, int lx, int rx, int vy, int ly, int ry) {
23        if (ly == ry) {
24            if (lx == rx)
25                tree[vx][vy] = data[lx][ly];
26            else
27                tree[vx][vy] = tree[vx * 2][vy] + tree[vx * 2 + 1][vy];
28        } else {
29            int my = (ly + ry) / 2;
30            buildY(vx, lx, rx, vy * 2, ly, my);
31            buildY(vx, lx, rx, vy * 2 + 1, my + 1, ry);
32            tree[vx][vy] = tree[vx][vy * 2] + tree[vx][vy * 2 + 1];
33        }
34    }
35
36    void buildX(int vx, int lx, int rx) {
37        if (lx != rx) {
38            int mx = (lx + rx) / 2;
39            buildX(vx * 2, lx, mx);
40            buildX(vx * 2 + 1, mx + 1, rx);
41        }
42        buildY(vx, lx, rx, 1, 0, cols - 1);
43    }
44
45    int queryY(int vx, int vy, int ly, int ry, int ql, int qr) {
46        if (ql > qr) return 0;
47        if (ql == ly && qr == ry) return tree[vx][vy];
48        int my = (ly + ry) / 2;
49        return queryY(vx, vy * 2, ly, my, ql, min(qr, my)) +
50               queryY(vx, vy * 2 + 1, my + 1, ry, max(ql, my + 1), qr);
51    }
52
53    int queryX(int vx, int lx, int rx, int qx1, int qx2, int qy1, int qy2) {
54        if (qx1 > qx2) return 0;
55        if (qx1 == lx && qx2 == rx)
56            return queryY(vx, 1, 0, cols - 1, qy1, qy2);
57        int mx = (lx + rx) / 2;
58        return queryX(vx * 2, lx, mx, qx1, min(qx2, mx), qy1, qy2) +
59               queryX(vx * 2 + 1, mx + 1, rx, max(qx1, mx + 1), qx2, qy1, qy2);
60    }
61};
62
63int main() {
64    vector<vector<int>> grid = {
65        {1, 2, 3},
66        {4, 5, 6},
67        {7, 8, 9}
68    };
69
70    SegmentTree2D st(grid);
71    cout << st.query(0, 0, 1, 1) << endl; // 1+2+4+5 = 12
72}

This is powerful, but it is not lightweight.

What a Quadtree Stores

A quadtree recursively divides 2D space into four quadrants. It is a spatial partitioning structure rather than a fixed-grid aggregation tree.

It is often used for:

point indexing
collision detection
region search
sparse spatial data

Instead of building on a fixed matrix shape, a quadtree subdivides only where needed.

A Minimal Quadtree Skeleton

cpp

1#include <iostream>
2#include <memory>
3#include <vector>
4using namespace std;
5
6struct Point {
7    int x, y;
8};
9
10struct Rect {
11    int x, y, w, h;
12
13    bool contains(const Point& p) const {
14        return p.x >= x && p.x < x + w && p.y >= y && p.y < y + h;
15    }
16};
17
18class QuadTree {
19public:
20    QuadTree(Rect boundary, int capacity)
21        : boundary(boundary), capacity(capacity), divided(false) {}
22
23    bool insert(const Point& p) {
24        if (!boundary.contains(p)) return false;
25        if (points.size() < capacity && !divided) {
26            points.push_back(p);
27            return true;
28        }
29        if (!divided) subdivide();
30        return nw->insert(p) || ne->insert(p) || sw->insert(p) || se->insert(p);
31    }
32
33private:
34    Rect boundary;
35    int capacity;
36    bool divided;
37    vector<Point> points;
38    unique_ptr<QuadTree> nw, ne, sw, se;
39
40    void subdivide() {
41        int hw = boundary.w / 2;
42        int hh = boundary.h / 2;
43        nw = make_unique<QuadTree>(Rect{boundary.x, boundary.y, hw, hh}, capacity);
44        ne = make_unique<QuadTree>(Rect{boundary.x + hw, boundary.y, hw, hh}, capacity);
45        sw = make_unique<QuadTree>(Rect{boundary.x, boundary.y + hh, hw, hh}, capacity);
46        se = make_unique<QuadTree>(Rect{boundary.x + hw, boundary.y + hh, hw, hh}, capacity);
47        divided = true;
48    }
49};

This is enough to show the spatial subdivision model, even though a full implementation would also include region queries.

When to Choose Which

Choose a 2D segment tree for fixed-grid rectangular range queries. Choose a quadtree for sparse geometric data and adaptive spatial partitioning.

Common Pitfalls

The biggest mistake is using a 2D segment tree for arbitrary scattered geometry when the real problem is spatial indexing. That often leads to more memory and complexity than necessary.

Another issue is expecting a quadtree to give the same rectangular aggregation behavior as a segment tree.

Developers also underestimate implementation complexity. Both structures are more subtle in 2D than simpler counterparts.

Finally, do not choose based only on asymptotic complexity. Data distribution, update pattern, and query type matter just as much.

Summary

A 2D segment tree is best for fixed-grid range aggregation queries.
A quadtree is better for sparse spatial partitioning and point-region work.
Segment trees trade memory and implementation cost for strong rectangular query support.
Quadtrees adapt to data distribution and often fit geometric workloads more naturally.
Pick the structure that matches the shape of the data, not just the name of the problem.

DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course

Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

2D Segment/Quad Tree Explanation with C

Data Structures & Algorithms practice on Codemia

Introduction

What a 2D Segment Tree Stores

A Small 2D Segment Tree Example

What a Quadtree Stores

A Minimal Quadtree Skeleton

When to Choose Which

Common Pitfalls

Summary

Related reading

DSA Fundamentals

Track what you have practised

Data Structures & Algorithms practice on Codemia