Yet Another Cute Segment Tree

Author Avatar
dozbear 11月 17, 2017
  • 在其它设备中阅读本文章

一直用一种很可爱的方法写线段树

好像是很久之前在哪看的(说白了就是zkw线段树……但是实现不那么一样)

range minimal query 为例

这是构建

int n, val[N * 2];

void build(int n, int* num) {
  for (int i = 0; i < n; i++) val[i + n] = num[i];
  for (int i = n - 1; i; i--) val[i] = min(val[i << 1], val[i << 1 | 1]);
}

如果要实现单点修改区间查询

那么把位置 p 的值修改为 k 的代码为

void modify(int p, int k) {
  for (val[p += n] = k; p; p >>= 1) val[p >> 1] = min(val[p], val[p ^ 1]);
}

查询 $[l,r)$ 中最小值的代码为

int query(int l, int r) {
  int res = INT_MAX;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) res = min(res, val[l++]);
    if (r & 1) res = min(res, val[--r]);
  }
  return res;
}

区间修改单点查询就是把上面代码改一下

事实上区间修改区间查询也能做,如果是取 min,那么区间查询的时候在 lr 的位置 pushdown 之后再区间查询就行(代码懒得放了)

还是放一下吧

int n, val[N * 2];
void build(int n, int* num) {
  for (int i = 0; i < n; i++) val[i + n] = num[i];
  for (int i = n - 1; i; i--) val[i] = min(val[i << 1], val[i << 1 | 1]);
}
void updval(int& c, int k) { c = min(c, k); }
void modify(int l, int r, int k) {
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) updval(val[l++], k);
    if (r & 1) updval(val[--r], k);
  }
}
void pushpath(int p) {
  if (!p) return;
  pushpath(p >> 1);
  updval(val[p << 1], val[p]);
  updval(val[p << 1 | 1], val[p]);
}
int query(int l, int r) {
  int res = INT_MAX;
  l += n, r += n;
  for (pushpath(l), pushpath(r - 1); l < r; l >>= 1, r >>= 1) {
    if (l & 1) updval(res, val[l++]);
    if (r & 1) updval(res, val[--r]);
  }
  return res;
}

这段代码是随手写的没有测试过!你看到自己也要判断!

要是区间加求区间和就维护一下每个节点有多少个孩子,要是区间加求最大/最小就在 modify 之后在原来的 lr 的位置做一个从下往上的 pushpath 的逆操作

类似这样

void pushup(int p) {
  for (; p; p >>= 1) val[p >> 1] = min(val[p], val[p ^ 1]);
}

和原来的单点 modify 很像对不对

按道理说大部分不用合并懒标记的的线段树的操作这样写都能做,但是考虑到编码复杂度最好只在简单的操作上用用

本作品采用 CC BY-NC-SA 4.0 Unported 进行许可
本文链接:https://dozbear.com/yet-another-cute-segment-tree/