线段树及其应用
Nick zheng
2 分钟阅读
# 线段树及其应用
## **特别声明: 以下仅为个人直观理解, 并不都正确严谨**
线段树($Segment Tree$), 顾名思义就是一颗节点由一条条"线段"构成的树. 这是一种十分高效的数据结构, 可以在$O(nlogn)$的时间复杂度内解决很多复杂的区间(单点)操作qaq.
考虑把一个区间分为两个长度相等的区间, 记为当前节点$u$的左孩子$u«1$和右孩子$u«1|1$($2n$ & $2n+1$). 那么我们可以分割需要修改/查询的区间为很多部分, 然后直到分割到叶子结点, 然后汇总/修改即可.
但是这样的时间复杂度并不优, 我们发现如果当前区间中有被完全包含的节点, 那么就可以直接使用其中提前汇总好的数据(或者使用懒标记$lazy$, 等到再次查询/修改的时候再下放给子节点), 从而优化时间复杂度为$O(nlogn)$.
那么我们需要一下几个函数来实现整个线段树的功能. 详见代码([P3372 【模板】线段树 1](https://www.luogu.com.cn/problem/P3372))qaq.
\#include<bits/stdc++.h>
\#define int long long
\#define md tr\[u].l+((tr\[u].r-tr\[u].l)>>1)//注意是当前节点的中点作为当前区间的分割线
using namespace std;
const int N=1e5+10;
struct node//节点
{
int l,r,data,lazy;
}tr\[N<<2];//一定要开四倍空间!!!
int a\[N];
void pushup(int u)//由子节点更新父节点的数据
{
tr\[u].data=tr\[u<<1].data+tr\[u<<1|1].data;
}
void pushdown(int u)//下放懒标记
{
tr\[u<<1].lazy+=tr\[u].lazy;
tr\[u<<1|1].lazy+=tr\[u].lazy;//懒标记直接传给下一代
tr\[u<<1].data+=tr\[u].lazy\*(tr\[u<<1].r-tr\[u<<1].l+1);
tr\[u<<1|1].data+=tr\[u].lazy\*(tr\[u<<1|1].r-tr\[u<<1|1].l+1);//孩子数据更新
tr\[u].lazy=0;//清空下放过的懒标记
}
void build(int u,int l,int r)//建树
{
if(l==r)//不能再分割了
{
tr\[u]={l,r,a\[l],0};//直接赋值
return;
}
tr\[u]={l,r,0,0};
int mid=md;
build(u<<1,l,mid);//递归左右孩子
build(u<<1|1,mid+1,r);
pushup(u);//一定不要忘了用子节点更新父节点(u)
}
void modify(int u,int l,int r,int x)//区间修改(单点修改可以看做l=r时的特殊情况)
{
if(r<tr\[u].l||l>tr\[u].r)//修改的区间不在当前节点范围内
{
return;
}
if(l<=tr\[u].l\&\&r>=tr\[u].r)//当前节点被完全包含于查询区间
{
tr\[u].lazy+=x;//打懒标记, 避免时间浪费
tr\[u].data+=x\*(tr\[u].r-tr\[u].l+1);//更新区间的汇总数据
return;
}
pushdown(u);//修改的时候一定要先下放懒标记qaq(有事有可能对修改有影响)!
modify(u<<1,l,r,x);//修改范围不用折半, 因为上面用if特判过了
modify(u<<1|1,l,r,x);
pushup(u);//修改完了一定要更新一下父节点
}
int query(int u,int l,int r)
{
if(r<tr\[u].l||l>tr\[u].r)//同理, 没被包含舍弃
{
return 0;
}
if(l<=tr\[u].l\&\&r>=tr\[u].r)//同理, 完全包含直接返回节点汇总值
{
return tr\[u].data;
}
pushdown(u);//查询时一定要下方懒标记才能查到真实值
return query(u<<1,l,r)+query(u<<1|1,l,r);//合并左右子树的数据, 注意查询区间不折半(同修改, 上面特判过了)
}
signed main()
{
int n,m;
scanf("%lld %lld",\&n,\&m);
for(int i=1;i<=n;i++)
{
scanf("%lld",\&a\[i]);
}
build(1,1,n);
for(int i=1;i<=m;i++)
{
int op,x,y;
scanf("%lld %lld %lld",\&op,\&x,\&y);
if(op==1)
{
int k;
scanf("%lld",\&k);
modify(1,x,y,k);//第一个参数是当前节点编号
}
else
{
printf("%lld\\n",query(1,x,y));
}
}
return 0;
}
以上是区间和的一个线段树, 其实线段树可以做更多操作, 只要这个操作符合以下对比表格:
...