Persistent 2D Segment Tree
By @antinloop · Published 2025-10-02
Problem: Tracking Points on a Massive 2D Grid Over Time
Imagine you’re building a geospatial tracking system. You want to monitor events on a grid that’s humongous—say, coordinates can go up to (10^9) in both X and Y.
You have to support two operations:
1. Add an event: A new event occurs at coordinates ((x, y)) with some value (like traffic density, pollution level, or score).
2. Query a rectangle: “What is the total sum of values inside rectangle ([x_1, x_2] \times [y_1, y_2]) at a specific version of the grid?”
Here’s the catch:
- The grid is sparse. Most cells are empty.
- You need to maintain historical versions, because you might want to query the grid as it looked yesterday, or before the last update.
- The coordinate range is huge. You cannot store a dense 2D array.
Goal: Handle updates and queries efficiently, even for a huge grid, while keeping all previous versions.
---
Solution in Words: Pointer-Based Persistent 2D Segment Tree
Here’s the intuitive solution:
1. Think in 1D first: Imagine a simple 1D segment tree that tracks sums along the X-axis. Each node represents a segment of X coordinates.
2. Add persistence: When you update a point, you don’t want to rebuild the whole tree. Instead, clone only the nodes along the path from root to the updated leaf. Other nodes are shared. This gives you a versioned tree efficiently.
3. Make it 2D: Each node in the X-tree now stores another segment tree for the Y-axis.
- So, each X-node holds a pointer to a Y-tree representing all points with X in that node’s range.
- Updating a point ((x, y)) means:
1. Walk down the X-tree along the path to x, cloning nodes.
2. For each X-node visited, update its Y-tree at y (also persistent).
4. Querying: To find the sum in rectangle [x1, x2] × [y1, y2] at a given version:
- Traverse the X-tree.
- If an X-segment is fully inside
[x1, x2], query the corresponding Y-tree for[y1, y2]. - Otherwise, descend recursively.
Why this works:
- Sparse storage: Only nodes with updates exist.
- Persistence: Each update produces a new version without touching other nodes.
- Time complexity: (O(\log X \cdot \log Y)) per update or query.
---
Solution in C++: Persistent 2D Segment Tree
Here’s a compact, clear C++ implementation with explanations:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// ----------------- Y-axis Tree -----------------
struct YNode {
ll sum;
YNode *l, *r;
YNode(ll s=0, YNode* L=nullptr, YNode* R=nullptr) : sum(s), l(L), r(R) {}
};
// update y-tree at pos by delta, returns new root
YNode* y_update(YNode* old, int yl, int yr, int pos, ll delta) {
if (pos < yl || pos > yr) return old;
YNode* node = new YNode();
if (old) *node = *old;
if (yl == yr) {
node->sum += delta;
return node;
}
int mid = yl + (yr - yl)/2;
if (pos <= mid)
node->l = y_update(old ? old->l : nullptr, yl, mid, pos, delta);
else
node->r = y_update(old ? old->r : nullptr, mid+1, yr, pos, delta);
node->sum = (node->l ? node->l->sum : 0) + (node->r ? node->r->sum : 0);
return node;
}
// query y-tree sum in [ql, qr]
ll y_query(YNode* node, int yl, int yr, int ql, int qr) {
if (!node || qr < yl || yr < ql) return 0;
if (ql <= yl && yr <= qr) return node->sum;
int mid = yl + (yr - yl)/2;
return y_query(node->l, yl, mid, ql, qr) + y_query(node->r, mid+1, yr, ql, qr);
}
// ----------------- X-axis Tree -----------------
struct XNode {
XNode *l, *r;
YNode *yroot;
XNode(XNode* L=nullptr, XNode* R=nullptr, YNode* Y=nullptr) : l(L), r(R), yroot(Y) {}
};
// update x-tree at posX, posY by delta
XNode* x_update(XNode* old, int xl, int xr, int posX, int posY, ll delta, int YL, int YR) {
XNode* node = new XNode();
if (old) *node = *old;
node->yroot = y_update(old ? old->yroot : nullptr, YL, YR, posY, delta);
if (xl == xr) return node;
int mid = xl + (xr - xl)/2;
if (posX <= mid)
node->l = x_update(old ? old->l : nullptr, xl, mid, posX, posY, delta, YL, YR);
else
node->r = x_update(old ? old->r : nullptr, mid+1, xr, posX, posY, delta, YL, YR);
return node;
}
// query rectangle sum
ll x_query(XNode* node, int xl, int xr, int qx1, int qx2, int qy1, int qy2, int YL, int YR) {
if (!node || qx2 < xl || xr < qx1) return 0;
if (qx1 <= xl && xr <= qx2)
return y_query(node->yroot, YL, YR, qy1, qy2);
int mid = xl + (xr - xl)/2;
return x_query(node->l, xl, mid, qx1, qx2, qy1, qy2, YL, YR)
+ x_query(node->r, mid+1, xr, qx1, qx2, qy1, qy2, YL, YR);
}
// ----------------- Demo -----------------
int main() {
const int XL=0, XR=15; // small demo grid
const int YL=0, YR=15;
vector<XNode*> versions;
versions.push_back(nullptr); // empty version 0
auto update_version = [&](int base_ver, int x, int y, ll delta){
XNode* newroot = x_update(versions[base_ver], XL, XR, x, y, delta, YL, YR);
versions.push_back(newroot);
return (int)versions.size()-1;
};
int v1 = update_version(0, 2, 3, 5); // (2,3) += 5
int v2 = update_version(v1, 7,10, 8); // (7,10) += 8
int v3 = update_version(v2, 2, 3, 4); // (2,3) += 4
auto rect_query = [&](int ver, int x1,int x2,int y1,int y2){
return x_query(versions[ver], XL, XR, x1,x2,y1,y2, YL,YR);
};
cout << "v1 sum [(0..5)x(0..5)] = " << rect_query(v1,0,5,0,5) << "\n"; // 5
cout << "v2 sum [(0..10)x(0..10)] = " << rect_query(v2,0,10,0,10) << "\n"; // 13
cout << "v3 sum [(2..2)x(3..3)] = " << rect_query(v3,2,2,3,3) << "\n"; // 9
return 0;
}
---
Why this approach is awesome
- Works for huge sparse grids without wasting memory.
- Supports versioning, so historical queries are easy.
- Updates and queries are fast:
O(log X * log Y)per operation. - Extensible: You can modify it to support max, min, or other aggregates instead of sum.