线段树 (Segement Tree)
线段树是用二叉树来表示一段区间的一种数据结构。
将区间分割成若干个单元区间，每个叶子结点对应一个单元区间。
根结点的权值值表示线段的总和sum[1];
结点i的权值表示其左右两子树的根的权值和，即sum[i]=sum[i*2]+sum[i*2+1];
重点:push_down(i);
int a[maxn],tree[4*maxn];
struct segmenttree{
int l,r;
long long sum，lztag;
}
void push_up(i){
tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;}
void push_down(int i){//修改操作仅仅是把要加的数放到了lztag上，并没有实时加到需要加的叶子结点上，所以每次修改需要push_down(i),查询也要push_down(i);
if(tree[i].lztag!=0){
tree[i*2].lztag+=tree[i*2+1].lztag;
tree[i*2+1].lztag+=tree[i*2+1].lztag;
tree[i*2].sum=(tree[i*2].r-tree[i*2].l+1) * tree[i].lztag；
tree[i*2+1].sum=(tree[i*2+1].r-tree[i*2+1].l+1) * tree[i].lztag;
tree[i].lztag=0;
}
}
用递归的方法建立一棵线段树：
void build(int i,int l,int r){
tree[i].l=l,tree[i].r=r;tree[i].lztag=0;;
if(l==r){
tree[i].sum=a[l];
return;}
int mid=(l+r)>>1;
build(i*2,l,mid);//递归建立左子树
build(i*2+1,mid+1,r);//递归建立右子树
push_up(i);//更新父节点
}
//线段树的建立
void add(int i,int l,int r,int k){
if(tree[i].l>=l&&tree[i].r<=r){
tree[i].sum+=(tree[i].r-tree[i].l+1)*k;//只是修改了i.sum,并没有传到叶子结点；
tree[i].lztag+=k;
}
push_down(i);
if(tree[i*2].r>=l) add(i*2,l,r,k);
if(tree[i*2+1].l<=r) add(i*2+1,l,r,k);
push_up(i);
}
long long search(int i,int l,int r){ //计算区间[l,r]的和
if(tree[i].l>r||tree[i].r<l) return 0;//查找的区间与当前结点所管辖的范围无交集，返回0；
if(tree[i].l=>l&&tree[i].r<=r) return tree[i].sum;
push_down(i);//
long long ts=0;//
if(tree[i*2].r>=l) ts+=search(i*2,l,r);
if(tree[i*2+1].l<=r) ts+=search(i*2+1,l,r);
return ts;
}
#include<bits/stdc++.h>
using namespace std;
const int MAXN =5e5+1000;
int ans;
struct node{
int l,r;
long long sum;
long long lztag;
}tree[4*MAXN];
int num[MAXN];
inline void build(int i,int l,int r){ //递归建立一棵二叉树
tree[i].l=l;tree[i].r=r;
tree[i].lztag=0;
if(l==r){
tree[i].sum=num[l];
return ;
}
int mid=(l+r)>>1;
build(i*2,l,mid);//构建左子树
build(i*2+1,mid+1,r);//右子树
tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//根结点的值等于子树的根的和
return ;
}
void push_down(int i);
void add(int i,int l,int r,int k){
if(tree[i].l>=l&&tree[i].r<=r){
tree[i].sum+=k*(tree[i].r-tree[i].l+1);//整个区间都加K
tree[i].lztag+=k;
return;
}
push_down(i);
if(tree[i*2].r>=l){
add(i*2,l,r,k);
}
if(tree[i*2+1].l<=r){
add(i*2+1,l,r,k);
}
tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
return ;
}
void push_down(int i){
if(tree[i].lztag!=0){
tree[i*2].lztag +=tree[i].lztag;
tree[i*2+1].lztag +=tree[i].lztag;
tree[i*2].sum +=(tree[i*2].r-tree[i*2].l+1) * tree[i].lztag;
tree[i*2+1].sum +=(tree[i*2+1].r-tree[i*2+1].l+1) * tree[i].lztag;
tree[i].lztag=0;
}
return ;
}
long long search(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);
long long s=0;
if(tree[i*2].r>=l){
s+=search(i*2,l,r);
}
if(tree[i*2+1].l<=r){
s+=search(i*2+1,l,r);
}
return s;
}
int main(){
int m,n;
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%d",&num[i]);
build(1,1,n);
while(m--){
int op;
cin>>op;
if(op==1){
int x,y,k;
cin>>x>>y>>k;
add(1,x,y,k);
}
if(op==2){
int x,y;
cin>>x;
long long res=0;
res=search(1,x,x);
printf("%lld\n",res);
}
}
return 0;
个人感觉push_down理解是个比较难的地方。
暂且理解为add先将区间莫一部分的sum进行了修改，push_down再把lztag传到其左右子数的根，并没有实时的修改叶子节点的sum值。
当你查询的区间，某一部分是叶子结点时，则需要push_down到叶子结点。
