这个系列终于更新了(主要因为树状数组初步比较成功)
话不多说，切入正题。
什么是线段树？
线段树是一种支持单点修改区间查询(树状数组也行) and 区间修改单点查询(树状数组不行) and 区间修改区间查询(树状数组更不行)的高级数据结构，相当于树状数组plus版。
——该图片来自百度百科
建树
我们先来看看怎么建树。线段树其实就是一个二叉树，每个人结点管辖一个区间。所以，我们开始可以建树了。左孩子有孩子分别递归一下，。
void build(int idx,int l,int r){
tree[idx].l=l;
tree[idx].r=r;
if(l==r){//如果这个节点是叶子节点
tree[i].sum=a[l];
return;
}
int mid=(l+r)>>1;
build(idx*2,l,mid);//分别构造左子树和右子树
build(idx*2+1,mid+1,r);
tree[idx].sum=tree[idx*2].sum+tree[idx*2+1].sum;
}顺便多一嘴，线段树一般开4倍空间(除非你动态开点)，但下面也有提及。
单点修改 区间查询
→单点修改
这个不难，直接向下递归就完事儿了。返回时按做就可以了。
void modify(int idx,int k,int x){
if(tree[idx].l==tree[idx].r){//找到了
tree[idx].sum+=x;
return;
}
if(k<=tree[idx*2].r)
modify(idx*2,k,x);
else
modify(idx*2+1,k,x);
tree[idx].sum=tree[idx*2].sum+tree[idx*2+1].sum;//返回更新
return;
}→区间查询
接下来我们看看如何区间查询。我们其实就找我们来看看哪些区间被目标区间包含了。所以，从根节点开始往下递归，如果当前结点是被要查询的区间包含了，则返回这个结点的信息，时间复杂度为。
int query(int idx,int l,int r){
if(tree[i].l>=l && tree[i].r<=r)//如果区间被包括在目标区间里面,直接返回
return tree[i].sum;
if(tree[i].r<l || tree[i].l>r)//八竿子打不着
return 0;
int res=0;
if(tree[idx*2].r>=l)
res+=query(idx*2,l,r);//左端点和目标区间有交集,搜左子树
if(tree[idx*2+1].l<=r)
res+=query(idx*2+1,l,r);//搜右子树
return res;
}
区间修改 单点查询
区间修改的话，就把这个区间加上一个k的标记 ，单点查询的时候，就从上跑到下，把沿路的标记加起来就好。
→区间修改
void modify(int idx,int l,int r,int k) {
if(tree[idx].l>=l && tree[idx].r<=r){
tree[idx].tag+=k;
return;
}
int mid=(tree[idx].l+tree[idx].r)>>1;
if(l<=mid)
modify(idx*2,l,r,k);
if(r>mid)
modify(idx*2+1,l,r,k);
}→单点查询
void query(int pos,int x){
int res+=tree[pos].tag;
if(tree[pos].l==tree[pos].r)
return res;
int mid=(tree[pos].l+tree[pos].r)>>1;
if(x<=mid)
query(pos<<1,x);
else
query(pos<<1|1,x);
}到这，你就可以去做洛谷P3368了。今天元宵节，我就不给你们挖坑了(其实是懒)。
#include <bits/stdc++.h>
using namespace std;
const int maxn=500005;
int ans;
int a[maxn];
struct node{
int l,r;
int num;
}tr[maxn*4];//线段树开四倍空间
void build(int p,int l,int r){
tr[p]={l,r,0};
if(l==r){
tr[p].num=a[l];
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void modify(int p,int l,int r,int k){
if(tr[p].l>=l && tr[p].r<=r){
tr[p].num+=k;
return;
}
int mid=(tr[p].l+tr[p].r)>>1;
if(l<=mid)
modify(p<<1,l,r,k);
if(r>mid)
modify(p<<1|1,l,r,k);
}
void query(int p,int x){
ans+=tr[p].num;
if(tr[p].l==tr[p].r)
return;
int mid=(tr[p].l+tr[p].r)>>1;
if(x<=mid)
query(p<<1,x);
else
query(p<<1|1,x);
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
for(int i=1;i<=m;i++){
int op;
cin>>op;
if(op==1){
int x,y,k;
cin>>x>>y>>k;
modify(1,x,y,k);
}
else{
ans=0;
int x;
cin>>x;
query(1,x);
cout<<ans<<endl;
}
}
return 0
}还是没忍住，挖了一个坑，你们自己找吧ψ(｀∇´)ψ
区间查询 区间修改(懒标记lazy tag)
读完这个，你才能说你会线段树。
当然，这个可以说是最难的一个part了。你可能会说把前面的代码直接拉来用不就结束了吗，但用不了多久你就会发现这个想法非常"智慧"。
那老办法行不通了，有什么新办法吗？当然有！它就是懒标记。懒标记是怎么个回事呢？还是刚刚
那张图。
比如我们要给[1,5]每一个加一，那么向下递归时，可以先不直接操作，而是将管辖那个区间的"领导"的值加上1*5。当然递归回去的时候不要忘记更新上面的结点。(不要问我为什么一定要这么干，因为我也不知道)
先看一下修改的代码。
void modify(int idx,int l,int r,int k){
if(tree[idx].r<=r && tree[idx].l>=l){
tree[idx].sum+=k*(tree[idx].r-tree[idx].l+1);
tree[idx].lazy+=k;//记录lazytag
return;
}
push_down(idx);//向下传递
if(tree[idx*2].r>=l)
modify(idx*2,l,r,k);
if(tree[idx*2+1].l<=r)
modify(idx*2+1,l,r,k);
tree[idx].sum=tree[idx*2].sum+tree[idx*2+1].sum;
return;
}这个是push_down的代码↓
void push_down(int idx){//清空lazytag
if(tree[idx].lazy!=0){
tree[idx*2].lazy+=tree[idx].lazy;
tree[idx*2+1].lazy+=tree[idx].lazy;
int mid=(tree[idx].l+tree[idx].r)/2;
tree[idx*2].sum+=tree[idx].lazy*(mid-tree[idx*2].l+1);
tree[idx*2+1].sum+=tree[idx].lazy*(tree[idx*2+1].r-mid);
tree[idx].lazy=0;//归零
}
return;
}那查询呢？一样。只要没有被完全包含在目标区间里就push_down，下放懒标记。并让每个区间加上。
int query(int i,int l,int r){
if(tree[i].l>=l && tree[i].r<=r)
return tree[i].sum;
if(tree[i].r<l || tree[i].l>r)
return 0;
push_down(i);
int res=0;
if(tree[i*2].r>=l)
res+=query(i*2,l,r);
if(tree[i*2+1].l<=r)
res+=query(i*2+1,l,r);
return res;
}ok，以上就是本期的全部内容。如果有什么问题，请在评论区指正。我们下期再见！
友情提醒:洛谷P3368的代码有问题，请不要无脑Ctrl C+Ctrl V
