如何用延迟传播实现段树？ [英] How to implement segment trees with lazy propagation?

问题描述

我在互联网上搜索了段落树的实现，但是在懒惰传播中没有发现任何东西。有一些以前的堆栈溢出问题，但他们专注于解决SPOJ的一些特殊问题。虽然我认为这是使用伪代码的段树的最佳解释，但是我需要用惰性传播实现它。我找到以下链接：

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。

现在，如果我要求您告诉我最大和最小数量，那么答案将是：

 最大= 10 
 
最低= -1 
  

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

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

任何人都可以给出一些很好的解释，包括用于延迟传播的伪代码在段树？

谢谢。

解决方案

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

1. 牺牲一点点内存来保存你的节点中的一个字段， li>
   
2. 为了检查节点是否已被传播以及是否必须创建其子节点，牺牲一点运行时间。

我坚持自己第一。检查分段树中的节点是否应该有子节点（ node-> lower_value！= node-> upper_value ）非常简单，但是您也必须检查这些子节点是否已经被构建（ node-> left_child，node-> right_child ），所以我引入了一个传播标志 node-> ;传播：

  typedef struct lazy_segment_node {
 int lower_value; 
 int upper_value; 
 
 struct lazy_segment_node * left_child; 
 struct lazy_segment_node * right_child; 
 
无符号字符传播; 
} lazy_segment_node; 
  

初始化

要初始化一个节点，使用指向节点指针（或 NULL ）的指针调用 initialize 和所需的 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; 
返回NULL; 
} 
 / *如果节点已被传播已经返回* / 
 if（node->传播）
返回节点; 
 
 / *节点不需要子节点，设置标志并返回* / 
 if（node-> upper_value == node-> lower_value）{
 node - >传播= 1; 
返回节点; 
} 
 
 / *跳过左右子创建，见下面的代码* / 
 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]创建一个延迟评估的段树。您可以看到，初次初始化后，测试没有子节点。通过使用访问，您实际生成那些子节点，并可以获取它们的值（如果这些子节点由分段树的逻辑存在）：

代码

  #include< stdlib.h> 
 #include< stdio.h> 
 
 typedef struct lazy_segment_node {
 int lower_value; 
 int upper_value; 
 
无符号字符传播; 
 
 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; 
返回NULL; 
} 
 if（node->传播）
返回节点; 
 
 if（node-> upper_value == node-> lower_value）{
 node-> propagated = 1; 
返回节点; 
} 
 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; 
返回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; 
返回NULL; 
} 
 node-> propagated = 1; 
返回节点; 
} 
 
 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\\\
）; 
 printf（test-> lower_value：％i\\\
，test-> lower_value）; 
 printf（test-> upper_value：％i\\\
，test-> upper_value）; 
 
 printf（\\\
Node not propagated\\\
）; 
 printf（test-> left_child：％p\\\
，test-> left_child）; 
 printf（test-> right_child：％p\\\
，test-> right_child）; 
 
 printf（\\\
Node传播与访问：\\\
）; 
 printf（access（test） - > left_child：％p\\\
，access（test） - > left_child）; 
 printf（access（test） - > right_child：％p\\\
，access（test） - > right_child）; 
 
 printf（\\\
Node传播与访问，但子类不是：\\\
）; 
 printf（access（test） - > left_child-> left_child：％p\\\
，access（test） - > left_child-> left_child）; 
 printf（access（test） - > left_child-> right_child：％p\\\
，access（test） - > left_child-> right_child）; 
 
 printf（\\\
Can使用subchilds上的访问：\\\
）; 
 printf（access（test-> left_child） - > left_child：％p\\\
，access（test-> left_child） - > left_child）; 
 printf（access（test-> left_child） - > right_child：％p\\\
，access（test-> left_child） - > right_child）; 
 
 printf（\可以链接：\\\
）; 
 printf（access（access（test） - > right_child） - > right_child） - > lower_value：％i\\\
，access（access（access（test） - > right_child） - > right_child） - > lower_value）; 
 printf（access（access（test） - > right_child） - > right_child） - > upper_value：％i\\\
，访问（访问（测试） - > 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）
 
节点传播与访问：
访问（测试） - > left_child：0x948e020 
访问（测试） - > right_child：0x948e038 
 
节点传播与访问，但子字典不是：
访问（测试） - > left_child-> left_child：（nil）
访问（测试） - > left_child-> right_child：（nil）
 
可以使用subchilds访问：
访问（test-> left_child） - > left_child：0x948e050 
访问（test-> left_child） - > right_child：0x948e068 
 
可以链接：
访问（test） - > right_child） - > right_child） - > lower_value：9 
访问（访问（访问（测试） - > right_child） - > right_child） - > upper_value：10 

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.topcoder.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.

Example

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 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.

Example with real data

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

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.

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

Thanks.

解决方案

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:

1. Sacrifice a little bit of memory to save a field in your node, which can be checked very easily
2. Sacrifice a little bit of runtime in order to check whether the node has been propagated and whether its child nodes have to be created.

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;

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.

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

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):

Code

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

Result (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

这篇关于如何用延迟传播实现段树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！