用 C++ 解释 2D 线段/四叉树 [关闭]

附：这可能不是重复的。我进行了搜索，并确保我没有得到我想要的东西。

我是一名 ACM 问题解决者，最近我学习了线性数组的线段树和具有延迟传播的线段树。但我遇到了一些需要 2D 线段树（在某处称为四叉树）的问题。但我找不到任何好的教程。我搜索了SO并找到了一个链接http://e-maxx.ru/algo/segment_tree http://e-maxx.ru/algo/segment_tree这是俄语教程。

我需要对 2D 线段树的源代码（最好是 C++）进行一些很好的解释。值得注意的是，我非常了解典型的线段树。

好吧，正如您所说，我希望您足够了解线段树（又名统计树）。我给出了多维线段树背后的一些直觉。

假设给你一个二维的N * N（对于相当大的 N，大到足以无法通过暴力处理）整数值网格，并且要求您执行操作 - 找到最小值/最大值或计算特定部分的所有项目的总和网格，更新任何网格索引值等。看起来，这个问题与典型的线段树问题没有什么不同，与数据容器的维度不同。这里可以选择构建一个 2D 线段树。

二维线段树的思想无非是四叉树 http://en.wikipedia.org/wiki/Quadtree- 树形数据结构，其中每个外部节点恰好有四个子节点。四叉树最常用于通过递归地将二维空间细分为四个象限或区域来划分二维空间。这些区域可以是正方形或矩形或者可以具有任意形状。 1974 年，Raphael Frinkel 和 J. L. Bentley 将这种数据结构命名为四叉树。类似的划分也称为Q-tree.

树的根包含完整的段[ (0, 0), (N - 1, N - 1) ]。对于每个细分市场[ (a1, b1), (a2, b2) ]，我们将它们分成[ (a1, b1), ( (a1 + a2) / 2, (b1 + b2) / 2 ) ) ], [ ( (a1 + a2) / 2 + 1, b1 ), ( a2, (b1 + b2) / 2 ) ], [ ( a1, (b1 + b2) / 2 + 1 ), ( (a1 + a2) / 2, b2 ) ] and [ ( (a1 + a2) / 2 + 1, (b1 + b2) / 2 + 1 ), ( a2, b2 ) ] until a1 = b1 and a2 = b2。构建线段树的成本为O(nlogn)并准备好线段树来回答RMQ（范围最大/最小查询）可以在O(logn).

假设，给你一个网格N = 4。那么对应的树将是 -

如您所见，4 * 4 array [ (0, 0), (3, 3) ]分为 4 个子数组 –[ (0, 0), (1, 1) ], [ (2, 0), (3, 1) ], [ (2, 0), (1, 3) ] and [ (2, 2), (3, 3) ]。进一步，每四个块又被分割成四个更小的单元；例如段[ (2, 2), (3, 3) ]将[ (2, 2), (2, 2) ], [ (3, 2), (3, 2) ], [ (2, 3), (2, 3) ] and [ (3, 3), (3, 3) ]。这些段是最小的单元，因此不再进一步划分。

执行

与分割部分不同，编码部分与线段树非常相似。这里给出的代码是编程竞赛友好的（没有指针、内存分配/释放内容和 OOP 结构），我在竞赛中多次使用了这个片段。

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 501
#define INF (1 << 30)
int P[Max][Max]; // container for 2D grid
 
/* 2D Segment Tree node */
struct Point {
    int x, y, mx;
    Point() {}
    Point(int x, int y, int mx) : x(x), y(y), mx(mx) {}
 
    bool operator < (const Point& other) const {
        return mx < other.mx;
    }
};
 
struct Segtree2d {

    // I didn't calculate the exact size needed in terms of 2D container size.
    // If anyone, please edit the answer.
    // It's just a safe size to store nodes for MAX * MAX 2D grids which won't cause stack overflow :)
    Point T[500000]; // TODO: calculate the accurate space needed
    
    int n, m;
 
    // initialize and construct segment tree
    void init(int n, int m) {
        this -> n = n;
        this -> m = m;
        build(1, 1, 1, n, m);
    }
 
    // build a 2D segment tree from data [ (a1, b1), (a2, b2) ]
    // Time: O(n logn)
    Point build(int node, int a1, int b1, int a2, int b2) {
        // out of range
        if (a1 > a2 or b1 > b2)
            return def();
 
        // if it is only a single index, assign value to node
        if (a1 == a2 and b1 == b2)
            return T[node] = Point(a1, b1, P[a1][b1]);
 
        // split the tree into four segments
        T[node] = def();
        T[node] = maxNode(T[node], build(4 * node - 2, a1, b1, (a1 + a2) / 2, (b1 + b2) / 2 ) );
        T[node] = maxNode(T[node], build(4 * node - 1, (a1 + a2) / 2 + 1, b1, a2, (b1 + b2) / 2 ));
        T[node] = maxNode(T[node], build(4 * node + 0, a1, (b1 + b2) / 2 + 1, (a1 + a2) / 2, b2) );
        T[node] = maxNode(T[node], build(4 * node + 1, (a1 + a2) / 2 + 1, (b1 + b2) / 2 + 1, a2, b2) );
        return T[node];
    }
 
    // helper function for query(int, int, int, int);
    Point query(int node, int a1, int b1, int a2, int b2, int x1, int y1, int x2, int y2) {
        // if we out of range, return dummy
        if (x1 > a2 or y1 > b2 or x2 < a1 or y2 < b1 or a1 > a2 or b1 > b2)
            return def();
 
        // if it is within range, return the node
        if (x1 <= a1 and y1 <= b1 and a2 <= x2 and b2 <= y2)
            return T[node];
 
        // split into four segments
        Point mx = def();
        mx = maxNode(mx, query(4 * node - 2, a1, b1, (a1 + a2) / 2, (b1 + b2) / 2, x1, y1, x2, y2) );
        mx = maxNode(mx, query(4 * node - 1, (a1 + a2) / 2 + 1, b1, a2, (b1 + b2) / 2, x1, y1, x2, y2) );
        mx = maxNode(mx, query(4 * node + 0, a1, (b1 + b2) / 2 + 1, (a1 + a2) / 2, b2, x1, y1, x2, y2) );
        mx = maxNode(mx, query(4 * node + 1, (a1 + a2) / 2 + 1, (b1 + b2) / 2 + 1, a2, b2, x1, y1, x2, y2));
 
        // return the maximum value
        return mx;
    }
 
    // query from range [ (x1, y1), (x2, y2) ]
    // Time: O(logn)
    Point query(int x1, int y1, int x2, int y2) {
        return query(1, 1, 1, n, m, x1, y1, x2, y2);
    }
 
    // helper function for update(int, int, int);
    Point update(int node, int a1, int b1, int a2, int b2, int x, int y, int value) {
        if (a1 > a2 or b1 > b2)
            return def();
 
        if (x > a2 or y > b2 or x < a1 or y < b1)
            return T[node];
 
        if (x == a1 and y == b1 and x == a2 and y == b2)
            return T[node] = Point(x, y, value);
 
        Point mx = def();
        mx = maxNode(mx, update(4 * node - 2, a1, b1, (a1 + a2) / 2, (b1 + b2) / 2, x, y, value) );
        mx = maxNode(mx, update(4 * node - 1, (a1 + a2) / 2 + 1, b1, a2, (b1 + b2) / 2, x, y, value));
        mx = maxNode(mx, update(4 * node + 0, a1, (b1 + b2) / 2 + 1, (a1 + a2) / 2, b2, x, y, value));
        mx = maxNode(mx, update(4 * node + 1, (a1 + a2) / 2 + 1, (b1 + b2) / 2 + 1, a2, b2, x, y, value) );
        return T[node] = mx;
    }
 
    // update the value of (x, y) index to 'value'
    // Time: O(logn)
    Point update(int x, int y, int value) {
        return update(1, 1, 1, n, m, x, y, value);
    }
 
    // utility functions; these functions are virtual because they will be overridden in child class
    virtual Point maxNode(Point a, Point b) {
        return max(a, b);
    }
 
    // dummy node
    virtual Point def() {
        return Point(0, 0, -INF);
    }
};
 
/* 2D Segment Tree for range minimum query; a override of Segtree2d class */
struct Segtree2dMin : Segtree2d {
    // overload maxNode() function to return minimum value
    Point maxNode(Point a, Point b) {
        return min(a, b);
    }
 
    Point def() {
        return Point(0, 0, INF);
    }
};
 
// initialize class objects
Segtree2d Tmax;
Segtree2dMin Tmin;
 
 
// Driver program.
int main(void) {
    int n, m;
    // input
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &P[i][j]);
 
    // initialize
    Tmax.init(n, m);
    Tmin.init(n, m);
 
    // query
    int x1, y1, x2, y2;
    scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
 
    Tmax.query(x1, y1, x2, y2).mx;
    Tmin.query(x1, y1, x2, y2).mx;
 
    // update
    int x, y, v;
    scanf("%d %d %d", &x, &y, &v);
    Tmax.update(x, y, v);
    Tmin.update(x, y, v);
 
    return 0;
}

3D分割

给你一个 3D 网格并要求你执行类似 2D 线段树的操作并非不可能。在这种情况下，我们可以像构建 2D 网格一样构建 3D 线段树。

我们将网格分成8个更小的部分，并递归地进行细分，直到出现最小的单元。下图展示了这种分割思想。

对于一维线段树，我们将数组分为 2 (2^1) 个线段，并生成log2(n)特定操作的复杂性。同样对于 2D 线段树，我们将每一步中的 2D 网格分成 4 (2^2) 段，这确保了每个操作log2(n)成本。因此，以类似的方式，我们通过将网格细分为 8 (2^3) 段来扩展此 3D 树。

P.S.：3D线段树是我自己的想象；我不知道是否有类似的事情。可能对于 2D 和 3D 线段树有更好的方法，但我认为这些代码足以用于编程竞赛，因为我已经使用过很多次了。

Edit:

3D分割的想法只不过是Octree http://en.wikipedia.org/wiki/Octree- 树形数据结构，其中每个内部节点恰好有八个子节点。八叉树最常用于通过递归地将三维空间细分为八个八分圆来划分三维空间。八叉树是四叉树的三维模拟。

八叉树经常用于 3D 图形和 3D 游戏引擎。它还有很多其他应用，例如空间索引、最近邻搜索、三维高效碰撞检测以及so many http://en.wikipedia.org/wiki/Octree#Application_to_color_quantization.

希望能帮助到你！