首页 > 其他分享 >笔记——线段树

笔记——线段树

时间:2023-10-04 22:34:32浏览次数:51  
标签:text 线段 mid 笔记 tag 区间 LL

蓝月の笔记——线段树篇

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

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

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,看在我码了这么多字的份上,你真的不点一个赞吗?

标签:text,线段,mid,笔记,tag,区间,LL
From: https://www.cnblogs.com/bluemoon-blog/p/17742514.html

相关文章

  • 线段树模板
    应该是做的最认真的模板了。。。namespacexds{template<classT,constintMYMAXSIZE,T(*fun)(Ta,Tb)>classSTree{private:Tt[MYMAXSIZE<<2],tag[MYMAXSIZE<<2],a[MYMAXSIZE];intnum;inlineconstintls(constintx){......
  • 【数据结构】- 线段树
    线段树简介线段树是可以维护区间信息的数据结构。线段树将每个长度不为\(1\)的区间划分成左右两个区间递归求解,故把整个线段划分为一个树形结构,通过合并左右两区间信息来求得该区间的信息。根据建树方式可分为普通线段树和动态开点线段树。根据区间信息可分为普通线段树......
  • Linux运维学习笔记
    此笔记为学习https://www.bilibili.com/video/BV1nW411L7xm/?vd_source=3f851e85e66ef33269a2eefee664cec2的学习记录,目前持续更新中,希望能找到运维的实习吖 O(≧▽≦)OLinux的终端终端组成部分Linux关机命令shoutdown-hnow(正常关机)halt(关闭内存)init0使用VMware备......
  • 活动报名与缴费小程序开发笔记一
    项目背景活动报名与缴费小程序的开发背景主要源于以下几个因素:1.数字化时代的需求:随着移动互联网和智能手机的普及,人们习惯使用手机进行各种活动。传统的纸质报名表格和线下缴费方式变得相对繁琐,而数字化报名与缴费小程序提供了更便捷的解决方案。2.提高效率和减少人力成本:对于活......
  • 流畅的python笔记 (二) 2.序列构成的数组
    内置序列类型分类1:容器序列(能存放不同类型):list,tuple,collections.deque扁平序列(不能存放不同类型):str,bytes,bytearray,memoryview,array.array分类2:可变序列(能被修改):list,bytearray,array.array,collections.deque,memoryview不可变序列:tuple,str,bytes列表推导......
  • Python笔记
    第一章、Python概述1.1 扩展库安装方法使用pip命令安装扩展库。在cmd命令行中输入pip,回车后可以看到pip命令的使用说明。1.2 常用的pip命令pip命令示例说明pipfreeze[>requirements.txt]列出已安装扩展库及其版本号(不知道怎么用。。?)pipinstallSomePacka......
  • note 线段树
    适用场景:不断区间修改、区间询问。假设我们要区间求和,\(tree\)的含义:区间的和,其两个子节点为这个区间分为两半的和。我们把一个数组\(a\)看作一颗树\(tree\),例:112333对应的\(tree\)(\(()\)里是编号,\([]\)里是对应的区间):(1)13[1,6]/......
  • 线段树专题复习
    今天的主题是线段树专题复习!(什么?是昨天的?不听不听,只要我不说都不知道我鸽了一天!)好了,言归正传,我们来看一下今天的知识点们吧。Part1线段树自己不想讲了,想看的移步其他博客想看踢我,今天没时间了Part2一些优化ZKW线段树俗称重口味线段树,是一种不用递归实现的线段树,常数和......
  • 【做题笔记】dp,但是国庆限定版
    Day1方块消除传送门看到这个数据范围就可以猜测正解是\(O(n^4)\)的dp,与这个差不多相符合的可以想到区间dp。然后大胆猜测一下就是区间dp,令\(dp[i][j]\)表示消除掉\([i,j]\)后的最大价值,这个显然可以从长度更短的区间转移过来。所以此题我们可以从区间dp的方向思考......
  • 《敏捷软件需求》阅读笔记一
    以下是关于敏捷软件需求这本书籍的前八章的阅读心得体会,涵盖了每章的主要观点和个人体会:第一章:敏捷方法概述    第一章介绍了敏捷方法的起源和核心原则,其中最关键的原则是个体与交互、工作的软件、客户合作和响应变化。我学到了敏捷方法的灵活性和迭代开发是应对不断变化......