我有搜索在互联网上关于实施段树却一无所获，当它来到懒惰的传播。有堆栈溢出一些previous的问题，但他们的重点是解决SPOJ的一些具体问题。虽然我觉得这是段树木伪code的最好解释，但我需要懒传播来实现它。我发现以下链接：

I have searched on internet about implementation of Segment trees but found nothing when it came to lazy propagation. There were some previous questions on stack overflow but they were focused on solving some particular problems of SPOJ. Though I think this is the best explanation of segment trees with pseudocode but I need to implement it with lazy propagation. I found following links :

http://community.top$c$cr.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Segment_Trees

在除了上述链接，一些博客也有，但他们都是以相同的线程给予参考

In addition to the above link, some blogs were also there but they all were giving reference to the same thread.

这是示例这个数据结构的应用程序会是这样，说我一直在考虑了一系列的数字从1到n。现在我做一些操作，比如增加一些常数，以一个特定范围或减去一些常数从一个特定的范围内。执行操作后我应该告诉的最小和最大数目，在给定的次数。

An example of the application of this data structure would be something like, say I have been given a range of numbers from 1 to n. Now I perform some operations like adding some constant number to a particular range or subtracting some constant number from a particular range. After performing operations I'm supposed to tell the minimum and maximum number in the given number.

这是的显而易见的解决方案将是由一个来执行加法或减法，以每数在给定范围内的一个。但这不能在一种情况，即不执行操作的大可行

An obvious solution would be to perform addition or subtraction to each number in the given range one by one. But this can't be feasible in a situation in which no of operations performed are large.

A 更好的办法将使用段树懒与繁殖技术。它说代替单独执行每个号码的更新操作，只跟踪所有的操作，直到所有的操作都​​完成。然后最后执行更新操作，以获得的最小和最大数目的范围内。

A better approach would be using Segment Trees with lazy propagation technique. It says instead of performing the update operation on each number individually, just keep track of all the operations until all operations are done. Then finally perform update operation to get the minimum and maximum number in the range.

示例用真实的数据

假设我已经给出的范围[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。

Suppose I have given the range [1,10] which means numbers are 1,2,3,4,5,6,7,8,9,10. Now suppose I perform an operation which decreases the numbers in the range [3,6] by 4 ,so now numbers will look like 1,2,-1,0,1,2,7,8,9,10. Now I perform another operation which increases the numbers in the range [5,9] by 1, so the number will now look like 1,2,-1,0,2,3,8,9,10,10.

现在，如果我请你告诉我，最大和最小数，那么答案将是：

Now if I ask you to tell me the maximum and minimum number then the answer will be :

Maximum = 10

Minimum = -1

这只是一个简单的example.The实际问题可能包含数千个这样的加/减operations.I希望很明显了。

This is just a simple example.The actual problem might contain thousands of such addition/subtraction operations.I hope it's clear now.

这是我所理解的那么远，但我想有这解释了这一概念和执行以更好的方式在互联网上没有统一的链接。

This is what I have understood so far but I guess there is no unified link on Internet which explains the concept and implementation in a better way.

任何人都可以提供一些很好的解释，包括伪code在段树懒传播？

Can anyone give some good explanation including pseudocode for lazy propagation in segment trees?

感谢。

推荐答案

延迟传播几乎总是包括某种形式的哨兵机制。你必须验证当前节点不需要传播，并且该检查应该很容易和快速。所以有两种可能性：

Lazy propagation almost always includes some kind of sentry-mechanism. You have to verify that the current node doesn't need to be propagated, and this check should be easy and fast. So there are two possibilities:

我贴自己的第一个。这是非常简单的检查在分段树中的节点是否有子节点（于节点＆GT;！lower_value =于节点＆GT; upper_value ），但你还必须检查这些子节点是否已经建立（于节点＆GT; left_child，于节点＆GT; right_child ），所以我介绍一个传播标志于节点＆GT ;传播：

I sticked myself to the first. It's very simple to check whether a node in a segmented tree should have child nodes (node->lower_value != node->upper_value), but you would also have to check whether those child node are already built (node->left_child, node->right_child), so I introduced a propagation flag 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 ：

Initialization

To initialize a node we call initialize with a pointer to the node pointer (or NULL) and the desired 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;
}

访问

到目前为止，没有什么特别的已经做了。这看起来像其他普通节点的创建方法。但是，为了创建实际的子节点，并设置传播标志，我们可以使用一个函数，这将返回相同节点上的指针，但它传播如果需要：

Access

So far nothing special has been done. This looks like every other generic node creation method. However, in order to create the actual child nodes and set the propagation flags we can use a function which will return a pointer on the same node, but propagates it if needed:

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;
}

正如你所看到的，一个传播节点将立即退出该功能。一个不传播节点，而不是首先检查是否它实际上应该包含子节点，然后在需要时创建它们。

As you can see, a propagated node will exit the function almost immediately. A not propagated node will instead first check whether it should actually contain child nodes and then create them if needed.

这其实是懒惰的评价。直到需要不创建子节点。需要注意的是 accessErr 还提供了一个额外的错误接口。如果你不需要它使用访问来代替：

This is actually the lazy-evaluation. You don't create the child nodes until needed. Note that accessErr also provides an additional error interface. If you don't need it use access instead:

lazy_segment_node * access(lazy_segment_node* node){
  return accessErr(node,NULL);
}

免费

为了释放这些元素，你可以使用一个通用的节点释放算法：

Free

In order to free those elements you can use a generic node deallocation algorithm:

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]一个懒惰的评估段树。你可以看到，第一次初始化后测试没有子节点。通过使用访问您实际生成的子节点，并能得到它们的值（如果这些子节点是否存在分段树的逻辑）：

Complete example

The following example will use the functions described above to create a lazy-evaluated segment tree based on the interval [1,10]. You can see that after the first initialization test has no child nodes. By using access you actually generate those child nodes and can get their values (if those child nodes exists by the segmented tree's logic):

#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）

Lazy evaluation test
test->lower_value: 1
test->upper_value: 10

Node not propagated
test->left_child: (nil)
test->right_child: (nil)

Node propagated with access:
access(test)->left_child: 0x948e020
access(test)->right_child: 0x948e038

Node propagated with access, but subchilds are not:
access(test)->left_child->left_child: (nil)
access(test)->left_child->right_child: (nil)

Can use access on subchilds:
access(test->left_child)->left_child: 0x948e050
access(test->left_child)->right_child: 0x948e068

It's possible to chain:
access(access(access(test)->right_child)->right_child)->lower_value: 9
access(access(access(test)->right_child)->right_child)->upper_value: 10