（烤肉）学习如何使用线段树

ppip · 2024-10-28 21:36:30 · 算法·理论

原文 / 关注不屈三叶虫喵，关注不屈三叶虫谢谢喵

省流：本文介绍一种简单实现的线段树及其原理，运行效率极高。另外还有其改为任意叉的扩展。

考虑给定一个区间的编号，对其建线段树。

抛弃传统二叉树形式，只是利用其编号：

分块，把编号 i 的点放进编号为 \lfloor i/2\rfloor 的块中。所有完整的块（块大小为 2）构成一个区间，对其递归建线段树。不完整的块，是这个区间的左右侧，是不完整的块，无需进入下一层。

你考虑做区间操作的时候会发生什么：如果左端点在散块，就暴力做这个散块，右端点同理。所以确实可以扔掉。

然后为了方便我们令初始区间为 [n,2n)，这样所有块的编号都是两两不同的（所有层的所有块）。这里选择这个区间的原因是我们需要保证 [l,r) 中 (r-1)/2<l，这是最小的区间。

然后我们发现此时等价线段树上 i 的父亲为 \lfloor i/2\rfloor。不过请注意，有些父亲不一定是有意义的，如果一个点被分到的块是散块，从而没有递归进入下一层，那么它没有父亲。

所以这个东西的结构其实是个森林，所有根的父亲其实是是没有用的，包括大多数时候的 1 号结点，所以在信息有顺序时不能用 1 表示全局信息！

所以单点修改同一般线段树，但我们不需要把所有叶子处理到同一层，只需要给编号 +\ n。

区间就是，把散块做了，然后递归到下一层，同块时停止，然后处理一下这个最后的块。

其实最后一个块不用这么复杂，因为每个块的大小显然不超过 2，所以只需要在 l=r 时停止（注意是左闭右开区间）。

具体实现：l \bmod 2\neq 0 时说明在一个散块中，r 也是一致的（这里体现左闭右开的好处）。散块大小显然为 1。

代码中为 0 开始的左闭右开区间。

void update(int x, int d) {
  for (x += n; x; x >>= 1) sgt[x] += d;
}
int query(int l, int r) {
  int ans = 0;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l&1) ans += sgt[l++];
    if (r&1) ans += sgt[--r];
  }
  return ans;
}

传统的 1 开始闭区间代码：

void update(int x, int d) {
  for (x += n - 1; x >= 1; x >>= 1) sgt[x] += d;
}
int query(int l, int r) {
  int ans = 0;
  for (l += n - 1, r += n - 1; l <= r; l >>= 1, r >>= 1) {
    if (l&1) ans += sgt[l++];
    if (~r&1) ans += sgt[r--];
  }
  return ans;
}

然后，这个东西也可以带标记（显然），甚至支持标记下传。对于单点操作，下传它的所有祖先；对于一个区间 [l,r]，下传 l 和 r 的所有祖先即可。

以上我们得到了一个非常好写且常数小的线段树。不过还可以进行一些更有意思的扩展：

我们发现这个东西没必要是二叉树：定义叉数为 b（b\ge 2），只需要将 \lfloor i/2\rfloor 改为 \lfloor i/b\rfloor，判散块的方法修改（以左端点为例：\lfloor i/2\rfloor=\lfloor (i-1)/b\rfloor 说明在一个散块中），以及处理最后的散块即可。

编号可以仍然取 [n,2n)，这肯定没问题。其实可以选择 \lfloor n/(b-1)\rfloor 为起始的左端点。

更进一步地，这个 b 甚至完全没必要是整数！我们以上的处理过程中完全未利用树结构的性质（叉数固定）。

所以稍加修改就可以获得一个任意实数叉线段树的代码：

void update(int x, int d) {
  for (x += n; x; x /= b) sgt[x] += d;
}
int query(int l, int r) {
  int ans = 0;
  for (l += n, r += n; int(l / b) != int(r / b); l /= b, r /= b) {
    while (int(l / b) == int((l - 1) / b)) ans += sgt[l++];
    while (int(r / b) == int((r - 1) / b)) ans += sgt[--r];
  }
  return accumulate(sgt + l, sgt + r, ans);
}