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:
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:
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
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.
