那些遇到过的问题

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

dar*_*dow 23 c algorithm tree data-structures

我在互联网上搜索了关于Segment树的实现但是在懒惰传播方面没有发现任何东西.之前有一些关于堆栈溢出的问题,但他们专注于解决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
Run Code Online (Sandbox Code Playgroud)

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

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

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

谢谢.

Zet*_*eta 19

懒惰传播几乎总是包含某种哨兵机制.您必须验证当前节点不需要传播,并且此检查应该简单快速.所以有两种可能性:

  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;
Run Code Online (Sandbox Code Playgroud)

初始化

要初始化一个节点,我们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;
}
Run Code Online (Sandbox Code Playgroud)

访问

到目前为止,没有做任何特别的事.这看起来像每个其他通用节点创建方法.但是,为了创建实际的子节点并设置传播标志,我们可以使用一个函数,它将在同一节点上返回一个指针,但如果需要则传播它:

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;
}
Run Code Online (Sandbox Code Playgroud)

如您所见,传播的节点几乎会立即退出该函数.未传播的节点将首先检查它是否应该实际包含子节点,然后在需要时创建它们.

这实际上是懒惰的评价.在需要之前,不要创建子节点.请注意,accessErr还提供了一个额外的错误接口.如果您不需要它,请使用access:

lazy_segment_node * access(lazy_segment_node* node){
  return accessErr(node,NULL);
}
Run Code Online (Sandbox Code Playgroud)

自由

为了释放这些元素,您可以使用通用节点解除分配算法:

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);
}
Run Code Online (Sandbox Code Playgroud)

完整的例子

以下示例将使用上述函数基于区间[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;
}
Run Code Online (Sandbox Code Playgroud)

结果(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

归档时间：

查看次数：

4849 次

最近记录：

10 年，5 月 前
相关归档
为什么将未使用的返回值转换为void？ 105
使用带有非null终止字符串的printf 97
什么是内核线程？ 25
C字符串连接的常量 21
给定一组n个整数,列出所有可能的子集,其中sum> = k 11
如何根据递归关系确定递归树的高度？ 10
实施押韵发现者 9
如何生成随机图？ 9
问题：在众多房屋中获得硬币或能量 7
JavaScript中多项选择测验的最佳数据结构 3
难疑归档
可以在JSON中使用注释吗？ 7104
如何让Git"忘记"一个被跟踪但现在位于.gitignore的文件？ 4888
如何异步上传文件？ 2841
检查字典中是否已存在给定键 2683
2048游戏的最佳算法是什么？ 1893
如何从Python字典中删除密钥？ 1539
将文件从主机复制到Docker容器 1391
为什么不从List <T>继承？ 1299
URL.Combine的URL？ 1186
你如何重命名Git标签？ 1162