程序员经验分享-hwhale

如何用惰性传播实现线段树？

2024-06-28

我在互联网上搜索了有关线段树的实现的信息，但在惰性传播方面却一无所获。之前有一些关于堆栈溢出的问题，但它们专注于解决 SPOJ 的一些特定问题。虽然我认为这是用伪代码对线段树的最好解释，但我需要用惰性传播来实现它。我发现以下链接：

除了上面的链接之外，还有一些博客，但它们都引用了同一个主题。

Example

An example这种数据结构的应用类似于，假设我得到了从 1 到 n 的数字范围。现在我执行一些操作，例如将一些常数添加到特定范围或从特定范围中减去一些常数。执行操作后，我应该告诉给定数字中的最小和最大数字。

An 明显的解决方案就是对给定范围内的每个数字进行一一加法或减法。但在没有执行大量操作的情况下，这是不可行的。

A 更好的方法将使用具有惰性传播技术的线段树。它表示不要单独对每个数字执行更新操作，只需跟踪所有操作，直到所有操作完成为止。然后最后进行更新操作，得到范围内的最小和最大数。

真实数据示例

假设我给出了范围 [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

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

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

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

Thanks.


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

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

Access

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

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

Free

为了释放这些元素，您可以使用通用节点释放算法：

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您实际上生成了这些子节点并可以获得它们的值（如果分段树的逻辑存在这些子节点）：

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) http://ideone.com/bNVDx 


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
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

c

Algorithm

datastructures

Tree

如何用惰性传播实现线段树？ 的相关文章

随机推荐

  • Python 常见问题解答：“异常有多快？”

    我只是在看Python常见问题解答 因为它在另一个问题中提到了 以前从未真正详细地看过它 我发现这个问题 http docs python org 3 faq design html how fast are exceptions 异常有多

  • 根据现有值更改 dataGridView 中的值

    我正在重新制作我的客户拥有的应用程序 这意味着我没有创建原始应用程序 其中一个请求是简化 dataGridView 之一中显示的数据 数据是从现有数据库中提取的 问题在于 在该显示器使用的数据表中 其中一列代表某种产品的一种使用类型 并由普

  • LaTeX 使用 hyperref 包和 natbib 更改文本引用的颜色

    我正在使用natbib https www ctan org pkg natbib and hyperref https www ctan org pkg hyperref我的 LaTeX 文档中包含了一些软件包 并且希望将超引用引文周围的

  • 为什么使用 MultiByteToWideCharArray 将 std::string 转换为 std::wstring？

    我想将 std string 转换为 std wstring 我遇到过两种方法 给定一个字符串 str 我们无法使用以下代码将其转换为宽字符串 wstring Widestring std wstring str begin str end

  • 根据多列删除重复项

    我使用以下内容列出了重复项 select s MessageId t from Message s join select ToUserId FromUserId count as qty from Message group by ToU

  • 如果我们不生成窗口，为什么定时器不起作用？

    这是代码 import java awt event ActionEvent import java awt event ActionListener import javax swing JFrame import javax swing

  • 在 django admin 中将 json 文本显示为友好列表

    我有一个 JSONField http djangosnippets org snippets 1478 http djangosnippets org snippets 1478 在模型中 我试图找出向管理员用户显示数据而不是 json

  • 如何从 JobDSL 脚本中访问 Jenkins 作业参数列表？

    我想保存传递到 JobDSL 作业的参数 我知道我可以引用各个参数 但我想让代码通用 我如何访问传递给作业的参数列表 当前的代码看起来像这样 final jobParameters new File parameters jobParame

  • 部署到 Heroku 时找不到“site”模块

    我正在尝试将 django 应用程序部署到 Heroku 但我不断收到错误 ImportError no module named site 我正在使用来自的自定义构建包https github com jiaaro heroku buil

  • 如何针对 Mac OS X 10.5 进行编译

    我想编译 10 5 及更高版本的应用程序 自从我升级到 Snow Leopard 并安装了最新的 XCode 后 gcc 默认为 10 6 我试过了 isysroot Developer SDKs MacOSX10 5 sdk但这似乎不起作

  • 使用 htaccess 禁用目录浏览

    在我的服务器中我有一系列文件夹 我会拒绝对所有这些文件夹的访问 我能怎么做 我必须使用什么规则 在 htaccess 根目录中添加一行 deny from all 问题 如果您想保留自己的访问权限 allow from 192 168 1

  • PrimeFaces 3.0.M3 单元编辑器不更新值

    我读过了there https stackoverflow com questions 6365877 cell edit in primefaces is not updating the value 6487361 6487361 但我

  • div 宽度，单位：厘米（英寸）

    我需要在每个显示器中放入宽度为 25 厘米 10 英寸 的站点 div 我怎样才能做到呢 您可以简单地使用cmCSS 中的单位 mydiv width 25cm 请注意 正如其他人指出的那样 结果仍然取决于操作系统对显示器尺寸的正确读取 S

  • 剥掉所有的身体标签而不毁掉他们的孩子

    此 Ruby 代码使用Nokogiri http nokogiri org doc xpath tbody remove 删除 的子项 tbody 以及 tbody 他们自己 我只想删除所有 tbody 文档中的标签 将其子项留在原处 我怎

  • HTML输入日期，如何减少日期和图标之间的间距？

    我需要压缩输入类型日期 所以我尝试将宽度设置为 120px 问题是有一个space日期数字和输入日期图标之间 我需要减少或删除该空间 有没有办法做到这一点 我的代码 顺便说一句 我正在使用 bootstrap 4

  • 你可以在 Android 中有意打开多个文件吗？

    我正在尝试在 Android Studio 中编写一个应用程序来打开多个音乐文件并存储它们的路径 目前我所做的只是一次加载一个文件 这不会出现任何问题 例如 下面的代码显示了我的加载按钮的 onclicklister 和相关代码 本示例的一

  • Java字符串对象的创建

    我一直在阅读 Java String 对象 并且有这个问题 String x a String y b 它在Java中创建两个对象吗 这两行代码不会创建任何对象 字符串文字 例如 a 被放入字符串池 https stackoverflow

  • enableHiveSupport 在 java Spark 代码中引发错误[重复]

    这个问题在这里已经有答案了 我有一个非常简单的应用程序 尝试使用 Spark 从 src main resources 读取 orc 文件 我不断收到此错误 无法实例化具有 Hive 支持的 SparkSession 因为找不到 Hive

  • 通过绑定启用 TabItem

    我想在不同页面是 TabItem 的应用程序中使用 MVVM 为此 我使用视图模型 项目 的可观察集合并将其绑定到选项卡控件 ItemSource 对于每个视图模型 我创建了一个单独的数据模板来呈现正确的视图 如下所示

  • 如何用惰性传播实现线段树？

    我在互联网上搜索了有关线段树的实现的信息 但在惰性传播方面却一无所获 之前有一些关于堆栈溢出的问题 但它们专注于解决 SPOJ 的一些特定问题 虽然我认为这是用伪代码对线段树的最好解释 但我需要用惰性传播来实现它 我发现以下链接 除了上面的

热门标签