AntInLoop

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.