使用C ++进行2D段/四叉树解释
PS这可能不重复。 我搜索了SO并确保我没有得到我想要的东西。
我是一个ACM问题求解器，最近我学习了线性数组的Segment Tree和延迟传播的Segment Tree。 但是我遇到了一些需要2D段树的问题（在某处被称为Quad树）。 但我找不到任何好的教程。 我搜索了SO并找到了一个链接http://e-maxx.ru/algo/segment_tree这是一个俄语教程。
我需要在2D段树上用源代码（最好用C ++）做一些很好的解释。 需要注意的是，我非常了解典型的分段树。
好吧，就像你说的那样，我希望你能够很好地了解分段树。 我在博客中给出了多维段树背后的一些直觉。
假设您给出了一个二维N * N （对于一个相当大的N，大到足以不被蛮力处理）整数值的网格，并且您被要求执行操作 – 找到最小值/最大值或计算网格特定部分的所有项目的总和，更新任何网格索引值等。看起来，问题与典型的分段树问题没有什么不同，与数据容器的维度不同。 这里可以选择的是构建2D段树。
2D分段树的概念只不过是Quad Tree – 一种树数据结构，其中每个外部节点恰好有四个子节点。 四叉树最常用于通过递归地将其细分为四个象限或区域来划分二维空间。 区域可以是正方形或矩形，或者可以具有任意形状。 数据结构在1974年由Raphael Frinkel和JL Bentley命名为四叉树。类似的分区也称为Q树 。
树的根包含通过[ (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 ) ]和[ ( (a1 + a2) / 2 + 1, (b1 + b2) / 2 + 1 ), ( a2, b2 ) ]直到a1 = b1和a2 = b2 。 构建分段树的成本是O(nlogn) ，并且分段树准备好回答RMQ（范围最大/最小查询）可以在O(logn) 。
假设您有一个N = 4的网格。 那么相应的树将是 –
如您所见， 4 * 4数组[ (0, 0), (3, 3) ]被分段为4个子数组 – [ (0, 0), (1, 1) ] ， [ (2, 0), (3, 1) ] ， [ (2, 0), (1, 3) ]和[ (2, 2), (3, 3) ] 。 而且，每个四个块被分成四个较小的单元; 例如，段[ (2, 2), (3, 3) ]将是[ (2, 2), (2, 2) ] ， [ (3, 2), (3, 2) ] ， [ (2, 3), (2, 3) ]和[ (3, 3), (3, 3) ] 。 这些细分市场是最小的单位，因此不再进一步划分。
履行
与分割部分不同，编码部分与分段树非常相似。 这里给出的代码是编程竞赛友好（没有指针，内存分配/释放内容和OOP结构），我在竞赛中多次使用这个代码片段。
#include 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; /* Drier 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分割几乎没有任何应用程序或它确实存在。 我只想对它有一些直觉。
给予3D网格并要求执行类似2D分段树的操作并非不可能。 在这种情况下，我们可以构建一个3D Segment树，就像我们对2D网格一样。
我们将网格划分为8个较小的段，并递归地进行细分，直到出现最小的单元。 下图显示了这种分割思想。
对于1D段树，我们将数组划分为2（2 ^ 1）个段，并且对于特定操作产生log2(n)复杂度。 同样对于2D分段树，我们将每个步骤中的2D网格分成4（2 ^ 2）个分段，这确保了每个操作的log2(n)成本。 因此，以类似的方式，我们通过将网格细分为8（2 ^ 3）个段来扩展此3D树。
PS：3D细分树是我自己的想象力; 我不知道是否有类似的东西。 对于2D和3D分段树可能有更好的方法，但我认为这些代码足以用于编程竞赛，因为我已经多次使用过这些代码。
编辑 ：
3D分割的想法只不过是八叉树 - 一种树数据结构，其中每个内部节点恰好有八个子节点。 八叉树最常用于通过递归地将其细分为八个八分圆来划分三维空间。 八叉树是四叉树的三维模拟。
八度通常用于3D图形和3D游戏引擎。 它有很多其他应用，如空间索引，最近邻搜索，三维高效碰撞检测等等 。
希望能帮助到你！