526互联

笔记——线段树

发布时间 2023-10-04 22:25:00作者: BluemoonQwQ

蓝月の笔记——线段树篇

在树状数组中，我们讲解了关于单点修改区间查询的操作。今天，我们要讲一种更加高级的数据结构，他解决的是区间修改区间查询的问题多了一个区间当然更高级啦。

这个数据结构就是——线段树

Luogu - P3372

给定一个长度为 \(n\) 的序列 \(a_1,a_2,\cdots,a_n\) 和两种操作：

  1. 输入 1 l r k，将 \([l,r]\) 区间里的每一个数加上 \(x\)；
  2. 输入 2 l r，求 \(\sum_{i=l}^{r}a_i\)。

这就是区间修改区间查询。

正片开始

先看图

【图片来源：OI-Wiki】

这就是线段树的建出来的树。所以我们就讲完了（逃

注意：线段树是一颗二叉树

所以讲解函数之前，我们要了解二叉树的子节点查看方法。

观察图，我可以看出：\(1\) 的子节点是 \(2(1 \times 2)\) 和 \(3(1 \times 2 + 1)\)，\(2\) 的子节点是 \(4(2 \times 2)\) 和 \(5(2 \times 2 + 1)\)，\(3\) 的子节点是 \(6(3 \times 2)\) 和 \(7(3 \times 2 + 1)\)。

以此类推，我们知道：编号为 \(i\) 的非叶子节点，\(i\) 的左儿子编号为 \(2 \times i\)，右儿子编号为 \(2 \times i + 1\)。用程序写出来就是：

int ls(int x) {
  return x << 1;
}
int rs(int x) {
  return x << 1 | 1;
}

这时候就有小朋友会问了，为什么这里会用到左移和或呢？

左移操作就是在二进制最后在加上一个 \(0\)，那每一个 \(1\) 都往前了一位，所以每个 \(1\) 代表的十进制数，就变成了原来的 \(2\) 倍。

因为左移完了之后最后一位必定为 \(0\)，将 \(0\) 或上 \(1\)，得到 \(1\)，这样我们就把最末尾的 \(0\) 改成了 \(1\)，所以就加上了 \(1\)。

所以 \(x << 1 = 2 \times x,x << 1 | 1 = 2 \times x + 1\)。

因为二叉树的节点个数接近于 \(4n\)，所以线段树

要开四倍空间！

要开四倍空间！！

要开四倍空间！！！

某位曹姓巨佬就因为没开四倍空间而挂掉。

为了方便，在下文的讲解和代码中，会采用以下名称：

  • \(t\) 数组，即线段树数组；
  • \(a\) 数组，即初始数组；
  • \(tag\) 数组，即存储 \(\text{tag}\) 的数组；
  • \(n\)，即初始数组的大小；
  • \(x\)，当前遍历到的节点编号；
  • \(l\)，当前遍历到的区间左端点；
  • \(r\)，当前遍历到的区间右端点；
  • \(mid\)，当前遍历到的区间中点；
  • \(ul\)，要修改的区间左端点；
  • \(ur\)，要修改的区间右端点；
  • \(x\)，要修改区间要加上的值；
  • \(ql\)，要查找的区间左端点；
  • \(qr\)，要查找的区间右端点。

接下来，我们就一个一个的来看线段树里面的函数吧！

\(\text{PushUp}\)

不多说，最简单也是最短的一个函数。

因为非叶子节点的和就是它的两个子节点的和，所以我们要把子节点的和上传到父亲节点。

代码：

void PushUp(int x) {
  t[x] = t[ls(x)] + r[rs(x)];
}

\(\text{Build}\)

从名字可以看出，就是建树，但是在建的过程中，还要将 \(\text{tag}\) 初始化一下。至于 \(\text{tag}\) 是什么，等我们讲到 \(\text{AddTag}\) 的时候再说。

我们来看建树的具体步骤：

  1. 初始化 \(\text{tag}\) 为 \(0\)；
  2. 如果当前节点只有一个数，那么直接更新；
  3. 继续遍历左右儿子；
  4. \(\text{PushDown}\) 更新 \(t_x\)。

代码：

void Build(LL x, LL l, LL r) {
  tag[x] = 0;
  if (l == r) {
    t[x] = a[l];
    return;
  }
  LL mid = (l + r) >> 1;
  Build(ls(x), l, mid), Build(rs(x), mid + 1, r);
  PushUp(x);
}

\(\text{ex_Update}\)

看到标题，就有小朋友会问了：“啊你这普通 \(\text{Update}\) 还没讲就来讲加强版干什么啊？”

我只想说，这里的 \(\text{ex}\) 不是指的加强，而是：恶心！

你想，你不用线段树暴力求解，你的 \(\text{Update}\) 的复杂度是 \(O(r-l+1)\) 也就是 \(O(n)\)。

但是你用这个 \(\text{ex_Update}\) 来修改的话，复杂度是 \(O(n \log n)\)，还不如暴力。

接下来，我们就来学习一下这个没用的 \(\text{ex_Update}\)

遍历到 \(x\) 这个区间时，有 \(2\) 种情况。

  1. 要修改的区间完全不在当前区间里，即 l > ur || r < ul，如果是这样直接跳过。
  2. 否则将这个区间加上它与要修改的区间重合部分乘要修改的值。

代码：

因为这个东西过于 \(\text{ex}\)，所以它被 \(\texttt{BLuemoon_}\) 删掉了。

\(\text{AddTag}\)

\(\text{tag}\) 就是解决 \(\text{ex_Update}\) 方法。

\(\text{tag}\)，全名 \(\text{lazy-tag}\)，懒标记。

\(\text{tag}\) 如其名，这就是为懒人准备的。

有多懒呢，你要更新一个区间，按道理你应该把这个节点的所有子节点，子节点的子节点，子节点的子节点的子节点……，全部遍历一遍，这就是 \(\text{ex_Update}\) 为什么复杂度甚至高于暴力的原因。

我们给某个点打上懒标记，并标记上此时的 \(k\) 是多少，然后把这个区间加上它应该加的就行了。

注意：这里的 \(\text{tag}\) 应该使用 += 来更新，因为它可能原来还有没有下穿的懒标记

代码：

void AddTag(int x, int l, int r, int p) {
  tag[x] += p, t[x] += p * (r - l + 1);
}

\(\text{PushDown}\)

下传懒标记。

如果这个点被标记了，那么它的所有子孙节点都应该加上对应的数，而我们只改了 \(t_x\) 的值，所以我们要不懒标记下传。步骤如下：

  1. 如果这个点没有懒标记，直接返回。
  2. 把左右儿子全部打上一样的懒标记。
  3. 把自己的懒标记清零。

注意：我们的 \(\text{tag}\) 存储的是 \(k\)，而不是 \(k \times (r - l + 1)\)，所以下传的时候不需要将原懒标记除以二，直接下传原懒标记即可。

代码：

void PushDown(LL x, LL l, LL r) {
  if (tag[x]) {
    LL mid = (l + r) >> 1;
    AddTag(ls(x), l, mid, tag[x]), AddTag(rs(x), mid + 1, r, tag[x]);
    tag[x] = 0;
  }
}

\(\text{Update}\)

这次是正经的 \(\text{Update}\) 了。

步骤：

  1. 如果要修改区间完全包含当前区间，则直接 \(\text{AddTag}\)，并返回。
  2. 下传标记，这里不需要判断有没有标记，\(\text{PushDown}\) 里面有判断。
  3. 如果左儿子和要修改区间有并集，则递归修改左儿子。
  4. 如果右儿子和要修改区间有并集，则递归修改右儿子。
  5. \(\text{PushUp}\)。

代码：

void Update(LL ul, LL ur, LL x, LL l, LL r, LL k) {
  if (ul <= l && r <= ur) {
    AddTag(x, l, r, k);
    return;
  }
  PushDown(x, l, r);
  LL mid = (l + r) >> 1;
  if (ul <= mid) {
    Update(ul, ur, ls(x), l, mid, k);
  }
  if (mid < ur) {
    Update(ul, ur, rs(x), mid + 1, r, k);
  }
  PushUp(x);
}

\(\text{Query}\)

加油！这已经是最后一个函数了。如果你看完这里，那么恭喜你，已经学会线段树了！

这也是唯一一个有返回值的函数，它返回的是 \(\sum_{i=l}^{r}a_i\)。不然呢？

步骤：

  1. 如果要查询区间完全包含当前区间，直接返回 \(t_x\)。
  2. 下传懒标记，一定不要忘了这一步，因为 \(\text{Update}\) 和 \(\text{Query}\) 是混着来的，在查询的时候也可能遇到没有下传的懒标记，如果不下传，那么就这递归就会让答案变小。
  3. 如果左儿子和要查询区间有并集，则递归查询左儿子，当前答案加上左儿子的和。
  4. 如果右儿子和要查询区间有并集，则递归查询右儿子，当前答案加上右儿子的和。
  5. 返回答案，这里不需要 \(\text{PushUp}\)。你自己都没有修改为什么要修改上面的

代码：

LL Query(LL ql, LL qr, LL x, LL l, LL r) {
  if (ql <= l && r <= qr) {
    return t[x];
  }
  PushDown(x, l, r);
  LL mid = (l + r) >> 1, ans = 0;
  if (ql <= mid) {
    ans += Query(ql, qr, ls(x), l, mid);
  }
  if (mid < qr) {
    ans += Query(ql, qr, rs(x), mid + 1, r);
  }
  return ans;
}

P3372完整代码

// J2023 | BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 1e5 + 5;

LL ls(LL x) {
  return x << 1;
}
LL rs(LL x) {
  return x << 1 | 1;
}

struct SegmentTree {
  LL n, a[kMaxN << 2], t[kMaxN << 2], tag[kMaxN << 2];
  void PushUp(LL x) {
    t[x] = t[ls(x)] + t[rs(x)];
  }
  void Build(LL x, LL l, LL r) {
    tag[x] = 0;
    if (l == r) {
      t[x] = a[l];
      return;
    }
    LL mid = (l + r) >> 1;
    Build(ls(x), l, mid), Build(rs(x), mid + 1, r);
    PushUp(x);
  }
  void AddTag(int x, int l, int r, int p) {
    tag[x] += p, t[x] += p * (r - l + 1);
  }
  void PushDown(LL x, LL l, LL r) {
    if (tag[x]) {
      LL mid = (l + r) >> 1;
      AddTag(ls(x), l, mid, tag[x]), AddTag(rs(x), mid + 1, r, tag[x]);
      tag[x] = 0;
    }
  }
  void Update(LL ul, LL ur, LL x, LL l, LL r, LL k) {
    if (ul <= l && r <= ur) {
      AddTag(x, l, r, k);
      return;
    }
    PushDown(x, l, r);
    LL mid = (l + r) >> 1;
    if (ul <= mid) {
      Update(ul, ur, ls(x), l, mid, k);
    }
    if (mid < ur) {
      Update(ul, ur, rs(x), mid + 1, r, k);
    }
    PushUp(x);
  }
  LL Query(LL ql, LL qr, LL x, LL l, LL r) {
    if (ql <= l && r <= qr) {
      return t[x];
    }
    PushDown(x, l, r);
    LL mid = (l + r) >> 1, ans = 0;
    if (ql <= mid) {
      ans += Query(ql, qr, ls(x), l, mid);
    }
    if (mid < qr) {
      ans += Query(ql, qr, rs(x), mid + 1, r);
    }
    return ans;
  }
};

SegmentTree tr;
LL m, op, x, y, k;

int main() {
  cin >> tr.n >> m;
  for (LL i = 1; i <= tr.n; i++) {
    cin >> tr.a[i];
  }
  tr.Build(1, 1, tr.n);
  for (; m; m--) {
    cin >> op;
    if (op == 1) {
      cin >> x >> y >> k;
      tr.Update(x, y, 1, 1, tr.n, k);
    } else {
      cin >> x >> y;
      cout << tr.Query(x, y, 1, 1, tr.n) << '\n';
    }
  }
  return 0;
}

线段树板子封装结构体：

struct SegmentTree {
  LL n, a[kMaxN << 2], t[kMaxN << 2], tag[kMaxN << 2];
  void PushUp(LL x) {
    t[x] = t[ls(x)] + t[rs(x)];
  }
  void Build(LL x, LL l, LL r) {
    tag[x] = 0;
    if (l == r) {
      t[x] = a[l];
      return;
    }
    LL mid = (l + r) >> 1;
    Build(ls(x), l, mid), Build(rs(x), mid + 1, r);
    PushUp(x);
  }
  void AddTag(int x, int l, int r, int p) {
    tag[x] += p, t[x] += p * (r - l + 1);
  }
  void PushDown(LL x, LL l, LL r) {
    if (tag[x]) {
      LL mid = (l + r) >> 1;
      AddTag(ls(x), l, mid, tag[x]), AddTag(rs(x), mid + 1, r, tag[x]);
      tag[x] = 0;
    }
  }
  void Update(LL ul, LL ur, LL x, LL l, LL r, LL k) {
    if (ul <= l && r <= ur) {
      AddTag(x, l, r, k);
      return;
    }
    PushDown(x, l, r);
    LL mid = (l + r) >> 1;
    if (ul <= mid) {
      Update(ul, ur, ls(x), l, mid, k);
    }
    if (mid < ur) {
      Update(ul, ur, rs(x), mid + 1, r, k);
    }
    PushUp(x);
  }
  LL Query(LL ql, LL qr, LL x, LL l, LL r) {
    if (ql <= l && r <= qr) {
      return t[x];
    }
    PushDown(x, l, r);
    LL mid = (l + r) >> 1, ans = 0;
    if (ql <= mid) {
      ans += Query(ql, qr, ls(x), l, mid);
    }
    if (mid < qr) {
      ans += Query(ql, qr, rs(x), mid + 1, r);
    }
    return ans;
  }
};

这样，你就学会了普通线段树的全部内容了，当然还有主席树，动态开点线段树，线段树合并，线段树分裂，李超线段树等等等等等等等等等等等等等……

当然，这些变种作者也不会

但是——

至少，你可以 AC 一道黄题了；至少，你可以在树状数组 TLE 的时候从容的写出一个线段树了；至少，你学会了一个 CCF \(5\) 级考点了；至少，你可以像某曹姓巨佬一样，只要看到数列就想到线段树了。

恭喜你，学会了线段树！

这就是本文的全部内容了，请帮我点一个赞然后关注我吗\(QwQ\)。

这篇文章的 Markdown 有428行，总字符数可以在标题下面看到，文件一共 \(12.2\) KB，看在我码了这么多字的份上，你真的不点一个赞吗？