线段树, 强大的数据结构, 用处也是比较广的.
首先, 我们要明白线段树是个啥?
线段树, 线段嘛, 有左右端点, 那么它当然可以代表一个区间, 那么区间上的好多事情都可以用它来搞, 比如: 区间加, 区间乘, 区间求和.
首先让我们先看个线段树的模型.
如图, 这就是一棵线段树的模型.
圈内的点表示这是第几个点, 红色表示这个点表示的区间范围.
每个点和它的左右两个儿子的编号是有一定的关系的:
点 N, 它的左儿子编号为 N$\times$2, 右儿子编号为 N$\times$2+1.
线段树支持单点修改, 区间修改, 单点查询, 区间查询.
讲解有易到难.
先放一张后边当例子讲解的图(每个圈中的数表示的为这个区间的和).
假设一段长度为 N 的序列, 那么我们需要维护总长为 1--N 的线段.
对于每一个点, 我们需要确定它所表示的线段的 左端点 右端点 以及我们要维护的区间和
对于每个点的左儿子和右儿子来说, 左儿子继承前一半 [L,(L+R)/2], 右儿子继承后一半( (L+R)/2,R ].
还有我们维护的区间和, 每个大区间都是有两个小区间组成, 那么 大区间的和 = 左儿子的和 + 右儿子的和.
这部分代码:
- struct ahah{
- long long l,r,sum,f; // 对于 f 的作用, 后边会有解释, 此处忽略.
}tree[200000<<2]; 注意此处四倍空间.
- void build(int k,int l,int r)
- {
- tree[k].l=l;tree[k].r=r;
- if(tree[k].l==tree[k].r)
- {
- scanf("%lld",&tree[k].sum);
- return ;
- }
- long long mid=(tree[k].l+tree[k].r)>>1;
- build(k<<1,l,mid);
- build(k<<1|1,mid+1,r);
- tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
- }
单点查询与修改
单点修改, 我们已知单点的位置, 那么我们从一号点开始, 根据两个儿子所代表的区间范围, 选择下一步是走左儿子还是右儿子, 今儿一步步的确定准确的点.
单点查询与单点修改几乎一样, 查询到具体的位置后, 输出其结果.
拿上边的图进行模拟下:
修改 4 号点: 左儿子 [0,4], 右儿子[5,8] -> 选择左儿子 ->左儿子 [0,2], 右儿子[3,4] -> 选择右儿子 ->... -> 找到 4 号点修改.
查询同上.
当我们修改完某个点以后, 包含这个点的区间的和发生了改变, 所以最后我们还要加一句:
$tree[k].sum=tree[k \times 2].sum+tree[k \times 2+1].sum$ 以确保维护的区间和不会改变.
代码: k 表示点的编号, 需要给 x 号点加上 y .
- void update(int k)
- {
- if(tree[k].l==tree[k].r)
- {
- tree[k].sum+=y;
- return ;
- }
- long long mid=(tree[k].l+tree[k].r)>>1;
- if(x<=mid)update(k<<1);
- else update(k<<1|1);
- tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
- }
区间求和与修改
区间修改与查询也有很大的相似.
区间修改, 暂时来说我们没有好办法, 只能一个一个的修改区间中的每一个元素, 后边会有优秀做法的讲解.
区间查询, 我们需要明确这个被查询的区间位置.
以下被查询的区间用 [a,b] 表示, k 表示当前的点的编号.
首先我们从最大的区间开始, 判断被查询的区间, 有三种情况:
1. 位于左儿子中 ($b \le tree[k<<1].l $) 还是右儿子中($a> tree[k<<1|1].l $), 然后选择下一步是去左儿子还是右儿子.
2. 被查询的区间被两部分都包括, 那么我们就将区间分开, 一部分查询左区间, 一部分查询右区间.
3. 现在的点所代表的区间 $(a <= tree[k].l , b>= tree[k].r )$ 被要查询的区间所包含, 那么不需要再查下去, 直接将答案加上这段区间所维护的和就好了.
拿查询区间 [3,5] 模拟一下:
mid 表示当前区间的二分点.
代码用递归实现:
- void query(int k)
- {
- if(x<=tree[k].l&&y>=tree[k].r)
- {
- ans+=tree[k].sum;
- return ;
- }
- if(tree[k].f)down(k); // 先省略就好.
- long long mid=(tree[k].l+tree[k].r)>>1;
- if(x<=mid)query(k<<1);
- if(y>mid)query(k<<1|1);
- }
重点来了: 懒标记
对于区间修改来说, 我们一个一个的修改浪费大量的时间, 并且修改了还不一定查修这个点, 为了解决这个问题, 我们引入懒标记 f .
首先我们要明确他的一个性质: 懒, 用得着的时候动一下, 用不着的时候就永远在那.
每个节点的的懒标记记录的是它所代表的这个区间所加的值 f .
就像区间查询一样, 当区间不被包含时, 分开查找, 当目前区间已被要修改的区间包含时, 那么我们就可以直接给这个点, 打上懒标记, 不需要去准确的一个一个的修改区间内的元素了.
那这样的话必究没法维护区间和了?
我们维护区间和为的是啥? 当然是为了求区间和了, 当我们在查询的时候, 若用得到这整个区间, 那么返回 维护的值 + 区间元素个数 $\times$ 懒标记的值, 若不全用得到的话, 那么我们将懒标记下传给它的左右两个儿子, 然后继续查找. 区间和并不是没有维护, 而是在维护懒标记从而间接地维护者区间和.
这里需要注意的是: 当节点的懒标记下传给儿子的时候它的懒标记则需要清空, 因为已经传给了儿子.
懒标记下传代码:
- void down(long long k)
- {
- tree[k<<1].f+=tree[k].f;
- tree[k<<1|1].f+=tree[k].f;
- tree[k<<1].sum+=(tree[k<<1].r-tree[k<<1].l+1)*tree[k].f;
- tree[k<<1|1].sum+=(tree[k<<1|1].r-tree[k<<1|1].l+1)*tree[k].f;
- tree[k].f=0;
- }
用到懒标记的区间加以及求和:
- void query(int k)
- {
- if(x<=tree[k].l&&y>=tree[k].r)
- {
- ans+=tree[k].sum;
- return ;
- }
- if(tree[k].f)down(k);
- long long mid=(tree[k].l+tree[k].r)>>1;
- if(x<=mid)query(k<<1);
- if(y>mid)query(k<<1|1);
- }
- void add(long long k)
- {
- if(tree[k].l>=x&&tree[k].r<=y)
- {
- tree[k].sum+=(tree[k].r-tree[k].l+1)*val;
- tree[k].f+=val;
- return ;
- }
- if(tree[k].f) down(k);
- long long mid=(tree[k].l+tree[k].r)>>1;
- if(x<=mid)add(k<<1);
- if(y>mid)add(k<<1|1);
- tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
- }
综上就是先对简单的线段树操作.
贴上模板:
- #include<cstdio>
- #include<iostream>
- using namespace std;
- long long n,m,ans,x,y,ch,val;
- struct ahah{
- long long l,r,sum,f;
- }tree[200000<<2];
- void build(int k,int l,int r)
- {
- tree[k].l=l;tree[k].r=r;
- if(tree[k].l==tree[k].r)
- {
- scanf("%lld",&tree[k].sum);
- return ;
- }
- long long mid=(tree[k].l+tree[k].r)>>1;
- build(k<<1,l,mid);
- build(k<<1|1,mid+1,r);
- tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
- }
- void update(int k)
- {
- if(tree[k].l==tree[k].r)
- {
- tree[k].sum+=y;
- return ;
- }
- long long mid=(tree[k].l+tree[k].r)>>1;
- if(x<=mid)update(k<<1);
- else update(k<<1|1);
- tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
- }
- void down(long long k)
- {
- tree[k<<1].f+=tree[k].f;
- tree[k<<1|1].f+=tree[k].f;
- tree[k<<1].sum+=(tree[k<<1].r-tree[k<<1].l+1)*tree[k].f;
- tree[k<<1|1].sum+=(tree[k<<1|1].r-tree[k<<1|1].l+1)*tree[k].f;
- tree[k].f=0;
- }
- void query(int k)
- {
- if(x<=tree[k].l&&y>=tree[k].r)
- {
- ans+=tree[k].sum;
- return ;
- }
- if(tree[k].f)down(k);
- long long mid=(tree[k].l+tree[k].r)>>1;
- if(x<=mid)query(k<<1);
- if(y>mid)query(k<<1|1);
- }
- void add(long long k)
- {
- if(tree[k].l>=x&&tree[k].r<=y)
- {
- tree[k].sum+=(tree[k].r-tree[k].l+1)*val;
- tree[k].f+=val;
- return ;
- }
- if(tree[k].f) down(k);
- long long mid=(tree[k].l+tree[k].r)>>1;
- if(x<=mid)add(k<<1);
- if(y>mid)add(k<<1|1);
- tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
- }
- int main()
- {
- scanf("%lld%lld",&n,&m);
- build(1,1,n);
- for(int i=1;i<=m;i++)
- {
- ans=0;
- cin>>ch>>x>>y;
- if(ch==1)
- {
- cin>>val;
- add(1);
- }
- else
- {
- query(1);
- cout<<ans<<"\n";
- }
- }
- }
例题:
入门
模板: 洛谷线段树 1: https://www.luogu.org/problemnew/show/P3372
单点修改与区间查询: 最大数 https://www.luogu.org/problemnew/show/P1198
进阶:
妖梦斩木棒: https://www.luogu.org/problemnew/show/P3797
无聊的数列: https://www.luogu.org/problemnew/show/P1438
来源: https://www.cnblogs.com/rmy020718/p/9571490.html