想改善这个问题吗?添加详细信息,并通过editing this post阐明问题。
6年前关闭。
Improve this question
附言这可能不是重复的。我搜寻了SO,确保没有得到想要的东西。
我是ACM问题解决者,最近我学习了线性阵列的分段树和具有延迟传播的分段树。但是我遇到了一些需要2D分段树(在某处称为四叉树)的问题。但是我找不到关于它的任何好的教程。我搜索了SO,并找到了http://e-maxx.ru/algo/segment_tree链接,它是俄语教程。
我需要在2D段树上使用源代码(最好是C++)进行一些很好的解释。要注意的是,我非常了解典型的段树。
最佳答案
好吧,正如您所说,我希望您对分段树足够了解。我在多维 segmentation 树from my blog后面提供了一些直觉。
假设您获得了一个二维的 N * N (对于一个很大的N,足够大,不能被蛮力处理)的整数值网格,并且要求您执行操作-找到最小值/最大值或计算网格特定部分的所有项目的总和,更新任何网格索引值等。似乎,该问题与典型的段树问题没有什么不同,与数据容器的维度不同。在这里可以选择构建2D分割树。
2D段树的概念不过是Quad Tree-树数据结构,其中每个外部节点恰好有四个子节点。四叉树最常用于通过将二维空间递归 segmentation 为四个象限或区域来划分二维空间。这些区域可以是正方形或矩形,或者可以具有任意形状。该数据结构在1974年由Raphael Frinkel和J. L. 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)
,并且在准备好段树的情况下,可以在O(logn)
中完成对RMQ(范围最大/最小查询)的回答。
假设给您一个网格,其中 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 <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;
/* 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分段树的类似操作。在这种情况下,我们可以像构造2D网格一样构造3D分割树。
我们将网格划分为8个较小的段,然后递归进行 segmentation ,直到出现最小的单位。下图显示了这种分割思路。
对于一维分段树,我们将数组分为2(2 ^ 1)个分段,这为特定操作产生了
log2(n)
复杂度。再次对于2D片段树,我们将2D网格的每一步都分成4(2 ^ 2)个片段,以确保每个操作的log2(n)
成本。因此,以类似的方式,我们通过将网格 segmentation 为8(2 ^ 3)个片段来扩展3D树。附注:3D分割树是我自己的想象力;我不知道有没有那样的东西。也许对于2D和3D分段树来说,还有更好的方法,但是我认为这些代码足以应付编程竞赛,因为我已经使用了很多次。
编辑:
3D分割的思想只不过是Octree,它是一种树数据结构,其中每个内部节点恰好有八个子节点。八进制通常用于通过将其递归 segmentation 为八个八分位数来划分三维空间。八叉树是四叉树的三维模拟。
八进制通常用于3D图形和3D游戏引擎中。它还具有许多其他应用程序,例如空间索引,最近邻居搜索,三维有效碰撞检测和so many。
希望能帮助到你!