c - 如果给定值小于当前值，则更新段树

Question

我一直想知道是否只有当更新的新值小于当前值时才可以更新段树。

例如。a[i]toa[j]是更新到 x

if(a[k]>x)
  a[k]=x;

i<=k<=j

如何才能做到这一点？

延迟传播是我正在尝试的。

Answer 1

我从您的问题中了解到的是，如果新值小于该值，您正在尝试更新数组的连续段，如果是，那么答案是段树。步骤应该是：

1-构造一个段树大小的数组（数组元素为2 * n -1 = n，由于段树是完整的二叉树，将有n-1个内部节点）并将其初始化为大于可能的最大值价值。

2-如果更新范围与段树的段范围完全匹配，则现在更新段树中段的值。例如，您想从值为 4 的 2-4 段进行更新，然后遍历以在段树中找到确切的段，该段可以是 2-4 作为单个段，也可以分为两个段，例如 2 和 3-4，只需更新部分。

3-对所有更新重复步骤 2（如果值小于段树中的当前值，则更新）。

4- 完成所有更新后，制作一个解析器，从上到下遍历整个段树，并降低 n 个叶节点的最小权重。