我在互联网上搜索了关于Segment树的实现但是在懒惰传播时没有发现任何东西。 之前有一些关于堆栈溢出的问题，但他们专注于解决SPOJ的一些特殊问题。 虽然我认为这是具有伪代码的分段树的最佳解释，但我需要使用延迟传播来实现它。 我发现以下链接：
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Segment_Trees
假设我给出了范围[1,10]，这意味着数字是1,2,3,4,5,6,7,8,9,10。 现在假设我执行的操作将范围[3,6]中的数字减少4，所以现在数字看起来像1,2，-1,0,1,2,7,8,9,10。 现在我执行另一个操作，将范围[5,9]中的数字增加1，因此数字现在看起来像1,2，-1,0,2,3,8,9,10,10。
懒惰传播几乎总是包含某种哨兵机制。 您必须validation当前节点不需要传播，并且此检查应该简单快速。 所以有两种可能性：
- 牺牲一点内存来保存节点中的字段，这可以很容易地检查
- 牺牲一点运行时间来检查节点是否已被传播以及是否必须创建其子节点。
我坚持到第一个。 检查分段树中的节点是否应该具有子节点（ node->lower_value != node->upper_value ）非常简单，但您还必须检查这些子节点是否已构建（ node->left_child, node->right_child ），所以我介绍了一个传播标志node->propagated ：
typedef struct lazy_segment_node{ int lower_value; int upper_value; struct lazy_segment_node * left_child; struct lazy_segment_node * right_child; unsigned char propagated; } lazy_segment_node;
初始化
要初始化一个节点，我们使用指向节点指针（或NULL ）和所需upper_value / lower_value的指针调用initialize ：
lazy_segment_node * initialize( lazy_segment_node ** mem, int lower_value, int upper_value ){ lazy_segment_node * tmp = NULL; if(mem != NULL) tmp = *mem; if(tmp == NULL) tmp = malloc(sizeof(lazy_segment_node)); if(tmp == NULL) return NULL; tmp->lower_value = lower_value; tmp->upper_value = upper_value; tmp->propagated = 0; tmp->left_child = NULL; tmp->right_child = NULL; if(mem != NULL) *mem = tmp; return tmp; }
访问
到目前为止还没有做任何特别的事。 这看起来像每个其他通用节点创建方法。 但是，为了创建实际的子节点并设置传播标志，我们可以使用一个函数，该函数将在同一节点上返回指针，但如果需要则传播它：
lazy_segment_node * accessErr(lazy_segment_node* node, int * error){ if(node == NULL){ if(error != NULL) *error = 1; return NULL; } /* if the node has been propagated already return it */ if(node->propagated) return node; /* the node doesn't need child nodes, set flag and return */ if(node->upper_value == node->lower_value){ node->propagated = 1; return node; } /* skipping left and right child creation, see code below*/ return node; }
如您所见，传播的节点几乎会立即退出该函数。 未传播的节点将首先检查它是否应该实际包含子节点，然后在需要时创建它们。
这实际上是懒惰的评价。 在需要之前，不要创建子节点。 请注意， accessErr还提供了一个额外的错误接口。 如果您不需要它，请改用：
lazy_segment_node * access(lazy_segment_node* node){ return accessErr(node,NULL); }
自由
为了释放这些元素，您可以使用通用节点解除分配算法：
void free_lazy_segment_tree(lazy_segment_node * root){ if(root == NULL) return; free_lazy_segment_tree(root->left_child); free_lazy_segment_tree(root->right_child); free(root); }
完整的例子
以下示例将使用上述函数基于区间[1,10]创建延迟评估的分段树。 您可以看到在第一次初始化test没有子节点。 通过使用access您实际生成了这些子节点并可以获取它们的值（如果这些子节点存在于分段树的逻辑中）：
码
#include #include typedef struct lazy_segment_node{ int lower_value; int upper_value; unsigned char propagated; struct lazy_segment_node * left_child; struct lazy_segment_node * right_child; } lazy_segment_node; lazy_segment_node * initialize(lazy_segment_node ** mem, int lower_value, int upper_value){ lazy_segment_node * tmp = NULL; if(mem != NULL) tmp = *mem; if(tmp == NULL) tmp = malloc(sizeof(lazy_segment_node)); if(tmp == NULL) return NULL; tmp->lower_value = lower_value; tmp->upper_value = upper_value; tmp->propagated = 0; tmp->left_child = NULL; tmp->right_child = NULL; if(mem != NULL) *mem = tmp; return tmp; } lazy_segment_node * accessErr(lazy_segment_node* node, int * error){ if(node == NULL){ if(error != NULL) *error = 1; return NULL; } if(node->propagated) return node; if(node->upper_value == node->lower_value){ node->propagated = 1; return node; } node->left_child = initialize(NULL,node->lower_value,(node->lower_value + node->upper_value)/2); if(node->left_child == NULL){ if(error != NULL) *error = 2; return NULL; } node->right_child = initialize(NULL,(node->lower_value + node->upper_value)/2 + 1,node->upper_value); if(node->right_child == NULL){ free(node->left_child); if(error != NULL) *error = 3; return NULL; } node->propagated = 1; return node; } lazy_segment_node * access(lazy_segment_node* node){ return accessErr(node,NULL); } void free_lazy_segment_tree(lazy_segment_node * root){ if(root == NULL) return; free_lazy_segment_tree(root->left_child); free_lazy_segment_tree(root->right_child); free(root); } int main(){ lazy_segment_node * test = NULL; initialize(&test,1,10); printf("Lazy evaluation test\n"); printf("test->lower_value: %i\n",test->lower_value); printf("test->upper_value: %i\n",test->upper_value); printf("\nNode not propagated\n"); printf("test->left_child: %p\n",test->left_child); printf("test->right_child: %p\n",test->right_child); printf("\nNode propagated with access:\n"); printf("access(test)->left_child: %p\n",access(test)->left_child); printf("access(test)->right_child: %p\n",access(test)->right_child); printf("\nNode propagated with access, but subchilds are not:\n"); printf("access(test)->left_child->left_child: %p\n",access(test)->left_child->left_child); printf("access(test)->left_child->right_child: %p\n",access(test)->left_child->right_child); printf("\nCan use access on subchilds:\n"); printf("access(test->left_child)->left_child: %p\n",access(test->left_child)->left_child); printf("access(test->left_child)->right_child: %p\n",access(test->left_child)->right_child); printf("\nIt's possible to chain:\n"); printf("access(access(access(test)->right_child)->right_child)->lower_value: %i\n",access(access(access(test)->right_child)->right_child)->lower_value); printf("access(access(access(test)->right_child)->right_child)->upper_value: %i\n",access(access(access(test)->right_child)->right_child)->upper_value); free_lazy_segment_tree(test); return 0; }
结果（ideone）
懒惰的评估测试
test-> lower_value：1
test-> upper_value：10
节点未传播
test-> left_child：（nil）
test-> right_child :(无）
通过访问传播的节点：
access（test） - > left_child：0x948e020
access（test） - > right_child：0x948e038
节点通过访问传播，但子节点不是：
access（test） - > left_child-> left_child：（nil）
access（test） - > left_child-> right_child：（nil）
可以在子子上使用访问权限：
access（test-> left_child） - > left_child：0x948e050
access（test-> left_child） - > right_child：0x948e068
可以链接：
访问（访问（访问（测试） - > right_child） - > right_child） - > lower_value：9
访问（访问（访问（测试） - > right_child） - > right_child） - > upper_value：10
如果有人在不使用结构的情况下寻找更简单的延迟传播代码：
（代码不言自明）
/** * In this code we have a very large array called arr, and very large set of operations * Operation #1: Increment the elements within range [i, j] with value val * Operation #2: Get max element within range [i, j] * Build tree: build_tree(1, 0, N-1) * Update tree: update_tree(1, 0, N-1, i, j, value) * Query tree: query_tree(1, 0, N-1, i, j) */ #include #include using namespace std; #include #include #define N 20 #define MAX (1+(1<<6)) // Why? :D #define inf 0x7fffffff int arr[N]; int tree[MAX]; int lazy[MAX]; /** * Build and init tree */ void build_tree(int node, int a, int b) { if(a > b) return; // Out of range if(a == b) { // Leaf node tree[node] = arr[a]; // Init value return; } build_tree(node*2, a, (a+b)/2); // Init left child build_tree(node*2+1, 1+(a+b)/2, b); // Init right child tree[node] = max(tree[node*2], tree[node*2+1]); // Init root value } /** * Increment elements within range [i, j] with value value */ void update_tree(int node, int a, int b, int i, int j, int value) { if(lazy[node] != 0) { // This node needs to be updated tree[node] += lazy[node]; // Update it if(a != b) { lazy[node*2] += lazy[node]; // Mark child as lazy lazy[node*2+1] += lazy[node]; // Mark child as lazy } lazy[node] = 0; // Reset it } if(a > b || a > j || b < i) // Current segment is not within range [i, j] return; if(a >= i && b <= j) { // Segment is fully within range tree[node] += value; if(a != b) { // Not leaf node lazy[node*2] += value; lazy[node*2+1] += value; } return; } update_tree(node*2, a, (a+b)/2, i, j, value); // Updating left child update_tree(1+node*2, 1+(a+b)/2, b, i, j, value); // Updating right child tree[node] = max(tree[node*2], tree[node*2+1]); // Updating root with max value } /** * Query tree to get max element value within range [i, j] */ int query_tree(int node, int a, int b, int i, int j) { if(a > b || a > j || b < i) return -inf; // Out of range if(lazy[node] != 0) { // This node needs to be updated tree[node] += lazy[node]; // Update it if(a != b) { lazy[node*2] += lazy[node]; // Mark child as lazy lazy[node*2+1] += lazy[node]; // Mark child as lazy } lazy[node] = 0; // Reset it } if(a >= i && b <= j) // Current segment is totally within range [i, j] return tree[node]; int q1 = query_tree(node*2, a, (a+b)/2, i, j); // Query left child int q2 = query_tree(1+node*2, 1+(a+b)/2, b, i, j); // Query right child int res = max(q1, q2); // Return final result return res; } int main() { for(int i = 0; i < N; i++) arr[i] = 1; build_tree(1, 0, N-1); memset(lazy, 0, sizeof lazy); update_tree(1, 0, N-1, 0, 6, 5); // Increment range [0, 6] by 5 update_tree(1, 0, N-1, 7, 10, 12); // Incremenet range [7, 10] by 12 update_tree(1, 0, N-1, 10, N-1, 100); // Increment range [10, N-1] by 100 cout << query_tree(1, 0, N-1, 0, N-1) << endl; // Get max element in range [0, N-1] }
请参阅此链接以获取更多解释段树和延迟传播
虽然我还没有成功解决它，但我相信这个问题比我们想象的容易得多。 您可能甚至不需要使用段树/间隔树…实际上，我尝试了两种方式来实现Segment Tree ，一种使用树结构，另一种使用数组，两种解决方案都快速获得了TLE。 我觉得可以用Greedy完成，但我还不确定。 无论如何，如果你想看看如何使用Segment Tree完成任务，请随时研究我的解决方案。 请注意， max_tree[1]和min_tree[1]对应于max/min 。
#include #include #include #include #include #include
使段树变得懒惰似乎没有任何优势。 最终，您需要查看每个单位坡度段的末端以获得最小值和最大值。 所以你不妨热切地扩展它们。
相反，只需修改标准段树定义即可。 树中的间隔将各自存储一个额外的整数d ，因此我们将写入[d; lo,hi] [d; lo,hi] 。 该树具有以下操作：
init(T, hi) // make a segment tree for the interval [0; 1,hi] split(T, x, d) // given there exists some interval [e; lo,hi], // in T where lo < x <= hi, replace this interval // with 2 new ones [e; lo,x-1] and [d; x,hi]; // if x==lo, then replace with [e+d; lo,hi]
现在，在初始化之后，我们使用两个拆分操作处理向子区间[lo,hi]添加d ：
split(T, lo, d); split(T, hi+1, -d);
这里的想法是我们将d添加到位置lo和右边的所有内容并再次将其减去hi+1和right。
构造树之后，在叶子上进行单个从左到右的传递，我们可以找到整数单位斜率段末端的值。 这就是我们计算最小值和最大值所需的全部内容。 更正式地说，如果树的叶间隔是[d_i; lo_i,hi_i] [d_i; lo_i,hi_i] ， i=1..n按从左到右的顺序，然后我们想要计算运行差D_i = sum{i=1..n} d_i然后L_i = lo_i + D_i和H_i = hi_i + D_i 。 在这个例子中，我们从[0; 1,10] [0; 1,10]然后在4处用d = -4和7分裂，其中d = + 4，得到[0; 1,2] [-4; 3,6] [4; 7,10] [0; 1,2] [-4; 3,6] [4; 7,10] [0; 1,2] [-4; 3,6] [4; 7,10] 。 然后L = [1,-1,7]并且H = [2, 2, 10] L = [1,-1,7] H = [2, 2, 10] 。 所以min是-1而max是10.这是一个简单的例子，但它一般都可以工作。
运行时间将是O（min（k log N，k ^ 2））其中N是最大初始范围值（在该示例中为10）并且k是所应用的操作的数量。 如果您在分割顺序方面运气非常差，则会发生k ^ 2情况。 如果随机化操作列表，预期时间将为O（k min（log N，log k））。
如果您有兴趣，我可以为您编写代码。 但如果没有兴趣，我不会。