我在互联网上搜索了关于分段树的实现，但在延迟传播方面一无所获。以前有一些关于堆栈溢出的问题，但它们集中于解决SPOJ的一些特定问题。虽然我认为这是用伪代码对分段树的最好解释，但我需要用延迟传播来实现它。我发现以下链接：
http://community.topcoder.com/tc?module=Static&d1=教程&d2=最低CommonAncestor#Segment_Trees
除了上面的链接，一些博客也在那里，但它们都引用了同一条线索。
示例
这个数据结构的应用程序的一个示例类似于，假设我得到了一个从1到n的数字范围。现在我执行一些操作，如将某个常数添加到特定范围或从特定范围减去某个常数。在执行操作后，我应该说出给定数字中的最小和最大数字。
显而易见的解决方案是对给定范围内的每个数字逐一执行加法或减法。但在没有大规模操作的情况下，这是不可行的。
更好的方法是使用具有延迟传播技术的分段树。它说，与其单独对每个号码执行更新操作，不如跟踪所有操作，直到所有操作完成。然后最后进行更新操作，得到该范围内的最小和最大数量。
实际数据示例
假设我给出了范围[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。
现在，如果我让你告诉我最大和最小数字，那么答案将是：
Maximum = 10
Minimum = -1
这只是一个简单的例子。实际问题可能包含数千个这样的加法/减法运算。我希望现在一切都清楚了。
到目前为止，我已经理解了这一点，但我想互联网上并没有统一的链接来更好地解释概念和实现。
有人能给出一些很好的解释吗？包括分段树中延迟传播的伪代码吗？
谢谢。
懒惰传播几乎总是包含某种哨兵机制。您必须验证当前节点是否需要传播，并且此检查应该简单快捷。因此有两种可能性：
- 牺牲一点内存来保存节点中的字段，这可以很容易地进行检查
- 牺牲一点运行时间来检查节点是否已经传播以及是否必须创建其子节点
我坚持第一个。检查分段树中的节点是否应该有子节点（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还提供了一个额外的错误接口。如果您不需要它，请使用access：
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 <stdlib.h>
#include <stdio.h>
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 testn");
printf("test->lower_value: %in",test->lower_value);
printf("test->upper_value: %in",test->upper_value);
printf("nNode not propagatedn");
printf("test->left_child: %pn",test->left_child);
printf("test->right_child: %pn",test->right_child);
printf("nNode propagated with access:n");
printf("access(test)->left_child: %pn",access(test)->left_child);
printf("access(test)->right_child: %pn",access(test)->right_child);
printf("nNode propagated with access, but subchilds are not:n");
printf("access(test)->left_child->left_child: %pn",access(test)->left_child->left_child);
printf("access(test)->left_child->right_child: %pn",access(test)->left_child->right_child);
printf("nCan use access on subchilds:n");
printf("access(test->left_child)->left_child: %pn",access(test->left_child)->left_child);
printf("access(test->left_child)->right_child: %pn",access(test->left_child)->right_child);
printf("nIt's possible to chain:n");
printf("access(access(access(test)->right_child)->right_child)->lower_value: %in",access(access(access(test)->right_child)->right_child)->lower_value);
printf("access(access(access(test)->right_child)->right_child)->upper_value: %in",access(access(access(test)->right_child)->right_child)->upper_value);
free_lazy_segment_tree(test);
return 0;
}
结果（表意）
懒惰评估测试test->lower_value:1测试->上限值：10节点未传播test->left_child:（nil）test->right_child:（零）使用访问权限传播的节点：访问（测试）->left_child:0x948e020访问（测试）->right_child:0x948e038节点通过访问进行传播，但子子代不是：访问（测试）->left_child->left_cild:（nil）访问（测试）->left_child->right_child:（nil）可以在子通道上使用访问权限：访问（测试->left_child）->left_child:0x948e050访问（测试->left_child）->right_child:0x948e068可以连锁：access（access（test）->right_child）->right_cild）->lower_value:9access（access（test）->right_child）->right_cchild）->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<iostream>
#include<algorithm>
using namespace std;
#include<string.h>
#include<math.h>
#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来完成，但我还不确定。不管怎样，如果你想看看使用分段树是如何完成的，请随时研究我的解决方案。注意，max_tree[1]和min_tree[1]对应于max/min。
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <utility>
#include <stack>
#include <deque>
#include <queue>
#include <fstream>
#include <functional>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#ifdef _WIN32 || _WIN64
#define getc_unlocked _fgetc_nolock
#endif
using namespace std;
const int MAX_RANGE = 1000000;
const int NIL = -(1 << 29);
int data[MAX_RANGE] = {0};
int min_tree[3 * MAX_RANGE + 1];
int max_tree[3 * MAX_RANGE + 1];
int added_to_interval[3 * MAX_RANGE + 1];
struct node {
int max_value;
int min_value;
int added;
node *left;
node *right;
};
node* build_tree(int l, int r, int values[]) {
node *root = new node;
root->added = 0;
if (l > r) {
return NULL;
}
else if (l == r) {
root->max_value = l + 1; // or values[l]
root->min_value = l + 1; // or values[l]
root->added = 0;
root->left = NULL;
root->right = NULL;
return root;
}
else {
root->left = build_tree(l, (l + r) / 2, values);
root->right = build_tree((l + r) / 2 + 1, r, values);
root->max_value = max(root->left->max_value, root->right->max_value);
root->min_value = min(root->left->min_value, root->right->min_value);
root->added = 0;
return root;
}
}
node* build_tree(int l, int r) {
node *root = new node;
root->added = 0;
if (l > r) {
return NULL;
}
else if (l == r) {
root->max_value = l + 1; // or values[l]
root->min_value = l + 1; // or values[l]
root->added = 0;
root->left = NULL;
root->right = NULL;
return root;
}
else {
root->left = build_tree(l, (l + r) / 2);
root->right = build_tree((l + r) / 2 + 1, r);
root->max_value = max(root->left->max_value, root->right->max_value);
root->min_value = min(root->left->min_value, root->right->min_value);
root->added = 0;
return root;
}
}
void update_tree(node* root, int begin, int end, int i, int j, int amount) {
// out of range
if (begin > end || begin > j || end < i) {
return;
}
// in update range (i, j)
else if (i <= begin && end <= j) {
root->max_value += amount;
root->min_value += amount;
root->added += amount;
}
else {
if (root->left == NULL && root->right == NULL) {
root->max_value = root->max_value + root->added;
root->min_value = root->min_value + root->added;
}
else if (root->right != NULL && root->left == NULL) {
update_tree(root->right, (begin + end) / 2 + 1, end, i, j, amount);
root->max_value = root->right->max_value + root->added;
root->min_value = root->right->min_value + root->added;
}
else if (root->left != NULL && root->right == NULL) {
update_tree(root->left, begin, (begin + end) / 2, i, j, amount);
root->max_value = root->left->max_value + root->added;
root->min_value = root->left->min_value + root->added;
}
else {
update_tree(root->right, (begin + end) / 2 + 1, end, i, j, amount);
update_tree(root->left, begin, (begin + end) / 2, i, j, amount);
root->max_value = max(root->left->max_value, root->right->max_value) + root->added;
root->min_value = min(root->left->min_value, root->right->min_value) + root->added;
}
}
}
void print_tree(node* root) {
if (root != NULL) {
print_tree(root->left);
cout << "t(max, min): " << root->max_value << ", " << root->min_value << endl;
print_tree(root->right);
}
}
void clean_up(node*& root) {
if (root != NULL) {
clean_up(root->left);
clean_up(root->right);
delete root;
root = NULL;
}
}
void update_bruteforce(int x, int y, int z, int &smallest, int &largest, int data[], int n) {
for (int i = x; i <= y; ++i) {
data[i] += z;
}
// update min/max
smallest = data[0];
largest = data[0];
for (int i = 0; i < n; ++i) {
if (data[i] < smallest) {
smallest = data[i];
}
if (data[i] > largest) {
largest = data[i];
}
}
}
void build_tree_as_array(int position, int left, int right) {
if (left > right) {
return;
}
else if (left == right) {
max_tree[position] = left + 1;
min_tree[position] = left + 1;
added_to_interval[position] = 0;
return;
}
else {
build_tree_as_array(position * 2, left, (left + right) / 2);
build_tree_as_array(position * 2 + 1, (left + right) / 2 + 1, right);
max_tree[position] = max(max_tree[position * 2], max_tree[position * 2 + 1]);
min_tree[position] = min(min_tree[position * 2], min_tree[position * 2 + 1]);
}
}
void update_tree_as_array(int position, int b, int e, int i, int j, int value) {
if (b > e || b > j || e < i) {
return;
}
else if (i <= b && e <= j) {
max_tree[position] += value;
min_tree[position] += value;
added_to_interval[position] += value;
return;
}
else {
int left_branch = 2 * position;
int right_branch = 2 * position + 1;
// make sure the array is ok
if (left_branch >= 2 * MAX_RANGE + 1 || right_branch >= 2 * MAX_RANGE + 1) {
max_tree[position] = max_tree[position] + added_to_interval[position];
min_tree[position] = min_tree[position] + added_to_interval[position];
return;
}
else if (max_tree[left_branch] == NIL && max_tree[right_branch] == NIL) {
max_tree[position] = max_tree[position] + added_to_interval[position];
min_tree[position] = min_tree[position] + added_to_interval[position];
return;
}
else if (max_tree[left_branch] != NIL && max_tree[right_branch] == NIL) {
update_tree_as_array(left_branch, b , (b + e) / 2 , i, j, value);
max_tree[position] = max_tree[left_branch] + added_to_interval[position];
min_tree[position] = min_tree[left_branch] + added_to_interval[position];
}
else if (max_tree[right_branch] != NIL && max_tree[left_branch] == NIL) {
update_tree_as_array(right_branch, (b + e) / 2 + 1 , e , i, j, value);
max_tree[position] = max_tree[right_branch] + added_to_interval[position];
min_tree[position] = min_tree[right_branch] + added_to_interval[position];
}
else {
update_tree_as_array(left_branch, b, (b + e) / 2 , i, j, value);
update_tree_as_array(right_branch, (b + e) / 2 + 1 , e , i, j, value);
max_tree[position] = max(max_tree[position * 2], max_tree[position * 2 + 1]) + added_to_interval[position];
min_tree[position] = min(min_tree[position * 2], min_tree[position * 2 + 1]) + added_to_interval[position];
}
}
}
void show_data(int data[], int n) {
cout << "[current data]n";
for (int i = 0; i < n; ++i) {
cout << data[i] << ", ";
}
cout << endl;
}
inline void input(int* n) {
char c = 0;
while (c < 33) {
c = getc_unlocked(stdin);
}
*n = 0;
while (c > 33) {
*n = (*n * 10) + c - '0';
c = getc_unlocked(stdin);
}
}
void handle_special_case(int m) {
int type;
int x;
int y;
int added_amount;
for (int i = 0; i < m; ++i) {
input(&type);
input(&x);
input(&y);
input(&added_amount);
}
printf("0n");
}
void find_largest_range_use_tree() {
int n;
int m;
int type;
int x;
int y;
int added_amount;
input(&n);
input(&m);
if (n == 1) {
handle_special_case(m);
return;
}
node *root = build_tree(0, n - 1);
for (int i = 0; i < m; ++i) {
input(&type);
input(&x);
input(&y);
input(&added_amount);
if (type == 1) {
added_amount *= 1;
}
else {
added_amount *= -1;
}
update_tree(root, 0, n - 1, x - 1, y - 1, added_amount);
}
printf("%dn", root->max_value - root->min_value);
}
void find_largest_range_use_array() {
int n;
int m;
int type;
int x;
int y;
int added_amount;
input(&n);
input(&m);
if (n == 1) {
handle_special_case(m);
return;
}
memset(min_tree, NIL, 3 * sizeof(int) * n + 1);
memset(max_tree, NIL, 3 * sizeof(int) * n + 1);
memset(added_to_interval, 0, 3 * sizeof(int) * n + 1);
build_tree_as_array(1, 0, n - 1);
for (int i = 0; i < m; ++i) {
input(&type);
input(&x);
input(&y);
input(&added_amount);
if (type == 1) {
added_amount *= 1;
}
else {
added_amount *= -1;
}
update_tree_as_array(1, 0, n - 1, x - 1, y - 1, added_amount);
}
printf("%dn", max_tree[1] - min_tree[1]);
}
void update_slow(int x, int y, int value) {
for (int i = x - 1; i < y; ++i) {
data[i] += value;
}
}
void find_largest_range_use_common_sense() {
int n;
int m;
int type;
int x;
int y;
int added_amount;
input(&n);
input(&m);
if (n == 1) {
handle_special_case(m);
return;
}
memset(data, 0, sizeof(int) * n);
for (int i = 0; i < m; ++i) {
input(&type);
input(&x);
input(&y);
input(&added_amount);
if (type == 1) {
added_amount *= 1;
}
else {
added_amount *= -1;
}
update_slow(x, y, added_amount);
}
// update min/max
int smallest = data[0] + 1;
int largest = data[0] + 1;
for (int i = 1; i < n; ++i) {
if (data[i] + i + 1 < smallest) {
smallest = data[i] + i + 1;
}
if (data[i] + i + 1 > largest) {
largest = data[i] + i + 1;
}
}
printf("%dn", largest - smallest);
}
void inout_range_of_data() {
int test_cases;
input(&test_cases);
while (test_cases--) {
find_largest_range_use_common_sense();
}
}
namespace unit_test {
void test_build_tree() {
for (int i = 0; i < MAX_RANGE; ++i) {
data[i] = i + 1;
}
node *root = build_tree(0, MAX_RANGE - 1, data);
print_tree(root);
}
void test_against_brute_force() {
// arrange
int number_of_operations = 100;
for (int i = 0; i < MAX_RANGE; ++i) {
data[i] = i + 1;
}
node *root = build_tree(0, MAX_RANGE - 1, data);
// print_tree(root);
// act
int operation;
int x;
int y;
int added_amount;
int smallest = 1;
int largest = MAX_RANGE;
// assert
while (number_of_operations--) {
operation = rand() % 2;
x = 1 + rand() % MAX_RANGE;
y = x + (rand() % (MAX_RANGE - x + 1));
added_amount = 1 + rand() % MAX_RANGE;
// cin >> operation >> x >> y >> added_amount;
if (operation == 1) {
added_amount *= 1;
}
else {
added_amount *= -1;
}
update_bruteforce(x - 1, y - 1, added_amount, smallest, largest, data, MAX_RANGE);
update_tree(root, 0, MAX_RANGE - 1, x - 1, y - 1, added_amount);
assert(largest == root->max_value);
assert(smallest == root->min_value);
for (int i = 0; i < MAX_RANGE; ++i) {
cout << data[i] << ", ";
}
cout << endl << endl;
cout << "correct:n";
cout << "t largest = " << largest << endl;
cout << "t smallest = " << smallest << endl;
cout << "testing:n";
cout << "t largest = " << root->max_value << endl;
cout << "t smallest = " << root->min_value << endl;
cout << "testing:n";
cout << "n------------------------------------------------------------n";
cout << "final result: " << largest - smallest << endl;
cin.get();
}
clean_up(root);
}
void test_automation() {
// arrange
int test_cases;
int number_of_operations = 100;
int n;
test_cases = 10000;
for (int i = 0; i < test_cases; ++i) {
n = i + 1;
int operation;
int x;
int y;
int added_amount;
int smallest = 1;
int largest = n;
// initialize data for brute-force
for (int i = 0; i < n; ++i) {
data[i] = i + 1;
}
// build tree
node *root = build_tree(0, n - 1, data);
for (int i = 0; i < number_of_operations; ++i) {
operation = rand() % 2;
x = 1 + rand() % n;
y = x + (rand() % (n - x + 1));
added_amount = 1 + rand() % n;
if (operation == 1) {
added_amount *= 1;
}
else {
added_amount *= -1;
}
update_bruteforce(x - 1, y - 1, added_amount, smallest, largest, data, n);
update_tree(root, 0, n - 1, x - 1, y - 1, added_amount);
assert(largest == root->max_value);
assert(smallest == root->min_value);
cout << endl << endl;
cout << "For n = " << n << endl;
cout << ", where data is : n";
for (int i = 0; i < n; ++i) {
cout << data[i] << ", ";
}
cout << endl;
cout << " and query is " << x - 1 << ", " << y - 1 << ", " << added_amount << endl;
cout << "correct:n";
cout << "t largest = " << largest << endl;
cout << "t smallest = " << smallest << endl;
cout << "testing:n";
cout << "t largest = " << root->max_value << endl;
cout << "t smallest = " << root->min_value << endl;
cout << "n------------------------------------------------------------n";
cout << "final result: " << largest - smallest << endl;
}
clean_up(root);
}
cout << "DONE............n";
}
void test_tree_as_array() {
// arrange
int test_cases;
int number_of_operations = 100;
int n;
test_cases = 1000;
for (int i = 0; i < test_cases; ++i) {
n = MAX_RANGE;
memset(min_tree, NIL, sizeof(min_tree));
memset(max_tree, NIL, sizeof(max_tree));
memset(added_to_interval, 0, sizeof(added_to_interval));
memset(data, 0, sizeof(data));
int operation;
int x;
int y;
int added_amount;
int smallest = 1;
int largest = n;
// initialize data for brute-force
for (int i = 0; i < n; ++i) {
data[i] = i + 1;
}
// build tree using array
build_tree_as_array(1, 0, n - 1);
for (int i = 0; i < number_of_operations; ++i) {
operation = rand() % 2;
x = 1 + rand() % n;
y = x + (rand() % (n - x + 1));
added_amount = 1 + rand() % n;
if (operation == 1) {
added_amount *= 1;
}
else {
added_amount *= -1;
}
update_bruteforce(x - 1, y - 1, added_amount, smallest, largest, data, n);
update_tree_as_array(1, 0, n - 1, x - 1, y - 1, added_amount);
//assert(max_tree[1] == largest);
//assert(min_tree[1] == smallest);
cout << endl << endl;
cout << "For n = " << n << endl;
// show_data(data, n);
cout << endl;
cout << " and query is " << x - 1 << ", " << y - 1 << ", " << added_amount << endl;
cout << "correct:n";
cout << "t largest = " << largest << endl;
cout << "t smallest = " << smallest << endl;
cout << "testing:n";
cout << "t largest = " << max_tree[1] << endl;
cout << "t smallest = " << min_tree[1] << endl;
cout << "n------------------------------------------------------------n";
cout << "final result: " << largest - smallest << endl;
cin.get();
}
}
cout << "DONE............n";
}
}
int main() {
// unit_test::test_against_brute_force();
// unit_test::test_automation();
// unit_test::test_tree_as_array();
inout_range_of_data();
return 0;
}
让分段树变懒似乎没有任何好处。最终，您需要查看每个单位坡度段的末端，以获得最小值和最大值。因此，您不妨急切地展开它们。
相反，只需修改标准段树定义。树中的每个间隔都将存储一个额外的整数d，因此我们将编写[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]
现在，在初始化之后，我们用两个拆分操作来处理将d添加到子区间[lo,hi]：
split(T, lo, d); split(T, hi+1, -d);
这里的想法是，我们将d添加到位置lo和右边的所有内容上，并再次减去hi+1和右边的内容。
树构造完成后，在叶子上从左到右的一次遍历可以让我们找到整数单位斜率段末端的值。这就是我们计算最小值和最大值所需要的全部内容。更正式地说，如果树的叶间隔从左到右依次为[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]开始，然后在d=-4的4和d=+4的7处拆分，得到[0; 1,2] [-4; 3,6] [4; 7,10]。然后是CCD_ 30和CCD_。所以最小值是-1，最大值是10。这是一个微不足道的例子，但它通常会起作用。
运行时间为O（min（k log N，k^2）），其中N是最大初始范围值（本例中为10），k是应用的操作数。如果您在分割排序时运气不好，则会出现k^2情况。如果将操作列表随机化，则预期时间将为O（k min（log N，log k））。
如果你感兴趣，我可以给你编个代码。但如果没有兴趣，我不会。
这是链接。它对具有延迟传播的分段树进行了实现和解释。虽然代码是用Java编写的，但这并不重要，因为只有两个函数"update"one_answers"query"，而且它们都是基于数组的。因此，这些函数也可以在C和C++中工作，而无需任何修改。
http://isharemylearning.blogspot.in/2012/08/lazy-propagation-in-segment-tree.html