如何实现带有延迟标记的线段树？

Question

我在网上搜索了一下线段树的实现方法，但是没有找到关于延迟传播的资料。虽然之前有一些关于解决SPOJ中特定问题的stackoverflow问题，但是它们都没有涉及延迟传播。尽管我认为这是用伪代码解释线段树的最佳方式，但我仍需要使用延迟传播实现它。我发现以下链接：

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#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

这只是一个简单的例子。实际问题可能包含成千上万个这样的加法/减法操作。我希望现在清楚了。

到目前为止，这就是我所理解的，但我想互联网上没有统一的链接以更好地解释概念和实现方法。

有人可以给出一个关于线段树中惰性传播的好解释，包括伪代码吗？

谢谢。

- dark_shadow

Answer 1

懒惰传播几乎总是包括某种哨兵机制。您必须验证当前节点是否需要传播，这个检查应该简单且快速。因此有两种可能性：

1. 为了节省一个可以很容易地检查的字段，在节点中牺牲一点内存
2. 为了检查节点是否已经传播以及其子节点是否需要创建，而在运行时稍微牺牲一些时间。

我坚持使用第一种方法。检查分段树中的节点是否应该具有子节点非常简单(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;

初始化

要初始化一个节点，我们需要调用initialize函数并传入节点指针（或NULL）和所需的upper_value/lower_value值：

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 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: (nil)
节点通过访问进行传递：
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
可以链式调用：
access(access(access(test)->right_child)->right_child)->lower_value: 9
access(access(access(test)->right_child)->right_child)->upper_value: 10

- Zeta

---

首先感谢您花费宝贵的时间回答我的问题。我有几个疑问想要讨论。首先，我学过使用数组实现线段树，这些数组操作就像堆数据结构一样。其次，您说我们只在需要时才创建左右子节点，但是在我给出的链接中，它说整棵树只在初始化时创建，但信息不会立即传播到叶子节点，它们保留在父节点中，并仅在最后一步传播。如果我错了，请指正我。 - dark_shadow

第一句：是的，目前它基于树形数据结构而不是数组。你可以通过一次性分配所有节点的内存来轻松更改这个问题。第二句：不，你是对的。我以为你只对树的惰性传播感兴趣，而不是实际查询的惰性评估，因为这是你标题的问题。在树中进行惰性传播意味着只有在需要时才创建值。你可以调整上述描述的相同机制以在数组中创建这样的效果，但是我怀疑在查询中没有不需要的值。 - Zeta

看一下我刚才在问题中介绍过的例子，也许它可以更好地说明我的意图。 - dark_shadow

你需要发布一个带有真实数据的实际例子。这还是太抽象了。我相信我开始理解你想要实现的东西，但是我从未真正研究过RMQ。也许我会在接下来的几天里编辑我的回答。 - Zeta

我尝试通过一个非常常见的例子来给出更多解释。如果仍然不清楚，请告诉我。 - dark_shadow

@code_hacker：我明白了，你想使用惰性求值来避免更新许多字段。我有一些方法，但这是离散数学（理论计算机科学）的问题，而我目前正忙于数值分析（有限元方法）。可能需要一段时间，抱歉 :/. - Zeta

Answer 2

如果有人在寻找更简单的延迟传播的代码，而且不使用结构体：

（代码很容易理解）

/**
 * 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 Trees and lazy propagation

- GorvGoyl

---

感谢提供博客链接。 - Charlie 木匠

Answer 3

虽然我还没有成功解决它，但我相信这个问题比我们想象的要简单得多。你可能甚至不需要使用Segment Tree/Interval Tree...实际上，我尝试了两种实现Segment Tree的方法，一种使用树结构，另一种使用数组，但两种解决方案都很快就超时了。我有一种感觉可以使用贪心算法来解决，但我还不确定。无论如何，如果你想看看如何使用Segment Tree来解决问题，请随意研究我的解决方案。请注意，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("0\n");
}

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("%d\n", 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("%d\n", 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("%d\n", 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;
}

- roxrook

Answer 4

在构建线段树时，似乎没有任何懒惰的优势。最终你需要查看每个单元斜率段的端点来获取最小值和最大值。所以你不妨急切地扩展它们。

相反，只需修改标准线段树的定义。树中的区间将额外存储一个整数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]开始，然后在4处进行d=-4的拆分，在7处进行d=+4的拆分，以获得[0; 1,2] [-4; 3,6] [4; 7,10]。然后L = [1,-1,7]和H = [2, 2, 10]。因此，最小值为-1，最大值为10。这是一个微不足道的例子，但它通常适用。

运行时间将为O(min(k log N, k^2)), 其中N是最大的初始范围值（在本例中为10），k是应用的操作数。如果拆分的顺序非常不幸，将会出现k^2的情况。如果对操作列表进行随机排序，则预期时间将为O(k min(log N, log k))。

如果您有兴趣，我可以为您编写代码。但如果没有兴趣，我就不会这样做。

- Gene

Answer 5

这是链接。它包含了带有延迟标记的线段树的实现和解释。虽然代码是用Java编写的，但并不重要，因为只有两个函数'update'和'query'，而且它们都是基于数组的。所以这些函数在C和C++中也可以直接使用，无需进行任何修改。

http://isharemylearning.blogspot.in/2012/08/lazy-propagation-in-segment-tree.html

- Bharat Kul Ratan