1. 首页
  2. 问题
  3. 如何实现具有延迟传播的段树？
一尘不染

如何实现具有延迟传播的段树？

algorithm

我曾在互联网上搜索过“段树”的实现，但在进行惰性传播时一无所获。以前有一些关于堆栈溢出的问题，但它们专注于解决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。

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

Maximum = 10

Minimum = -1

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

到目前为止，这是我所了解的，但是我想Internet上没有统一的链接可以更好地解释概念和实现。

谁能给出一些很好的解释，包括用于段树中延迟传播的伪代码？

谢谢。


阅读 223

收藏
2020-07-28

共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 ：（无）
test-> right_child ：（无）

通过访问传播的节点：
访问（测试）-> left_child：0x948e020
访问（测试）-> right_child：0x948e038

节点随访问而传播，但子节点不是：
访问（测试）-> left_child-> left_child：（无）
访问（测试）-> left_child-> right_child ：（无）

可以对子孩子使用访问权限：
访问（test-> left_child）-> left_child：0x948e050
访问（test-> left_child）-> right_child：0x948e068

可以链接：
access（访问（access（test）-> right_child）-> right_child）->下限值：9
access（访问（访问（测试）-> right_child）-> right_child）->上限值：10
2020-07-28