推广到更高维

线段树可以非常自然地推广到更高维。

在一维情况下，我们把数组的下标划分成区间。

在二维情况下，可以：

先针对第一维下标构建一棵普通线段树，然后对这棵树中的每一个区间，再针对第二维下标建立一棵普通线段树。

简单二维线段树

给定矩阵 $a[0\dots n-1,\ 0\dots m-1]$ ，我们希望：

求某个子矩阵 $a[x_1\dots x_2,\ y_1\dots y_2]$ 中的和（或者最小值／最大值）。
修改矩阵中的单个元素，即执行 $a[x][y]=p$ 。

于是，我们建立一棵二维线段树：先对第一维坐标 $x$ 建线段树，再对第二维坐标 $y$ 建线段树。

为了更容易理解构建过程，可以暂时忘记矩阵是二维的，只保留第一维坐标。

首先仅利用第一维坐标，构建一棵普通的一维线段树。但是，与其在每个区间中保存一个数，不如保存一整棵线段树。也就是说，这时重新考虑第二维坐标。由于第一维坐标已经固定在区间 $[l\dots r)$ 中，因此实际上是在处理条带 $a[l\dots r,\ 0\dots m-1]$ 并为它建立一棵线段树。

下面是二维线段树的构建实现。实际上包含两个相互独立的部分：

沿 $x$ 坐标构建线段树：build_x；
沿 $y$ 坐标构建线段树：build_y。

对于 build_y 中的叶节点，需要区分两种情况：

第一维当前区间 $[tlx\dots trx]$ 的长度为 $1$ ；
长度大于 $1$ 。

第一种情况下，直接取矩阵中对应的值。

第二种情况下，可以把 $x$ 方向两个子节点中的线段树值进行合并。

void build_y(int vx, int lx, int rx, int vy, int ly, int ry) {
    if (ry - ly == 1) {
        if (rx - lx == 1)
            t[vx][vy] = a[lx][ly];
        else
            t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
    } else {
        int my = (ly + ry) / 2;
        build_y(vx, lx, rx, vy*2, ly, my);
        build_y(vx, lx, rx, vy*2+1, my, ry);
        t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
    }
}

void build_x(int vx, int lx, int rx) {
    if (rx - lx > 1) {
        int mx = (lx + rx) / 2;
        build_x(vx*2, lx, mx);
        build_x(vx*2+1, mx, rx);
    }
    build_y(vx, lx, rx, 1, 0, m);
}

这样的线段树仍然使用线性数量的内存，不过常数更大： $16nm$ 。显然，上面描述的 build_x 过程同样在线性时间内工作。

现在考虑查询。

二维查询仍然使用相同的思想：

首先在第一维坐标上拆分查询区间，然后对每个访问到的节点，调用对应的第二维线段树。

int sum_y(int vx, int vy, int tly, int try_, int ly, int ry) {
    if (ry <= tly || try_ <= ly)
        return 0;
    if (ly <= tly && try_ <= ry)
        return t[vx][vy];
    int tmy = (tly + try_) / 2;
    return sum_y(vx, vy*2, tly, tmy, ly, ry)
         + sum_y(vx, vy*2+1, tmy, try_, ly, ry);
}

int sum_x(int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
    if (rx <= tlx || trx <= lx)
        return 0;
    if (lx <= tlx && trx <= rx)
        return sum_y(vx, 1, 0, m, ly, ry);
    int tmx = (tlx + trx) / 2;
    return sum_x(vx*2, tlx, tmx, lx, rx, ly, ry)
         + sum_x(vx*2+1, tmx, trx, lx, rx, ly, ry);
}

这个函数的运行时间为 $O(\log n\log m)$ 。

因为它首先在第一维线段树上向下搜索，而对于第一维中每一个访问到的节点，又要在对应的第二维线段树中执行一次查询。最后考虑修改查询。我们希望根据某个元素的变化 $a[x][y]=p$ 更新线段树。

显然，第一棵线段树中只会修改那些覆盖坐标 $x$ 的节点，一共有 $O(\log n)$ 个。

对于这些节点所对应的第二维线段树，又只需要修改覆盖 $y$ 的节点，一共有 $O(\log m)$ 个。

因此，实现与一维情况没有太大区别，只不过首先沿第一维下降，然后沿第二维下降。

void update_y(int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, int new_val) {
    if (ry - ly == 1) {
        if (rx - lx == 1)
            t[vx][vy] = new_val;
        else
            t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
    } else {
        int my = (ly + ry) / 2;
        if (y <= my)
            update_y(vx, lx, rx, vy*2, ly, my, x, y, new_val);
        else
            update_y(vx, lx, rx, vy*2+1, my, ry, x, y, new_val);
        t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
    }
}

void update_x(int vx, int lx, int rx, int x, int y, int new_val) {
    if (rx - lx > 1) {
        int mx = (lx + rx) / 2;
        if (x <= mx)
            update_x(vx*2, lx, mx, x, y, new_val);
        else
            update_x(vx*2+1, mx, rx, x, y, new_val);
    }
    update_y(vx, lx, rx, 1, 0, m, x, y, new_val);
}

二维线段树的压缩

考虑如下问题：

平面上有 $n$ 个点，它们的坐标为

(x_i,y_i),

需要回答这样的查询：

统计位于矩形
$((x_1,y_1),(x_2,y_2))$
内的点的数量。

显然，对于这种问题，如果构建包含

O(n^2)

个元素的二维线段树，会造成非常严重的浪费。

大量内存实际上都不会被使用。

因为每一个点在第一维线段树中只会属于

O(\log n)

个区间。

因此，第二维所有线段树区间真正“有用”的总大小只有

O(n\log n).

所以可以这样做：

对于第一维线段树中的每一个节点，只利用当前第一维区间中实际出现的第二维坐标来构建第二维线段树。

换句话说：

在为编号为 $vx$ 、边界为 $tlx$ 、 $trx$ 的某个节点构建内部线段树时，只考虑满足

x\in[tlx,trx]

的点，然后仅使用这些点构建第二维线段树。

这样，每一棵第二维线段树所占用的空间就恰好与实际需要的空间一致。

最终，总内存会下降到

O(n\log n).

仍然可以在

O(\log^2 n)

时间内回答查询。

只需要在第二维坐标上再进行一次二分查找，而这不会改变整体复杂度。

不过，这种结构无法支持修改操作。

如果出现一个新的点，就需要在某一棵第二维线段树的中间插入一个新的元素，而这无法高效完成。

最后需要指出：

通过以上方式压缩后的二维线段树，实际上几乎等价于前面的一维线段树变形——在每个节点中保存一个子数组。

特别地，二维线段树只是“在线段树每个节点中保存一个子数组”这一思想的一个特殊情况。

因此，如果因为某种查询无法实现而不得不放弃二维线段树，那么可以考虑把内部线段树替换成更加强大的数据结构，例如笛卡尔树。

简单二维线段树​

二维线段树的压缩

简单二维线段树