线段树+单点修改

骑猪看日落 2021-12-09 15:45 352阅读 0赞

洛谷P3347

已知一个数列，你需要进行下面两种操作：

1.将某一个数加上x

2.求出某区间每一个数的和

## 输入输出格式 ##

**输入格式：**

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3个整数，表示一个操作，具体如下：

操作1： 格式：1 x k 含义：将第x个数加上k

操作2： 格式：2 x y 含义：输出区间\[x,y\]内每个数的和

**输出格式：**

输出包含若干行整数，即为所有操作2的结果。

## 输入输出样例 ##

**输入样例\#1：** 复制

5 5
    1 5 4 2 3
    1 1 3
    2 2 5
    1 3 -1
    1 4 2
    2 1 4

**输出样例\#1：** 复制

14
    16

## 说明 ##

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=8，M<=10

对于70%的数据：N<=10000，M<=10000

对于100%的数据：N<=500000，M<=500000

样例说明：

![2256.png][]

故输出结果14、16

#include<bits/stdc++.h>
    using namespace std;
    int n,m,d[501000]; 
    struct Node{
    	int l,r,v,sum;//lr是区间的左右边界，v是这个节点的值，sum是这个区间的和 
    }t[501000*4];//注意：这里为什么要开四倍空间
    void build(int k,int l,int r){ //建立线段树 
    	t[k].l=l;
    	t[k].r=r; 
    	if(l==r){
    		t[k].sum=t[k].v=d[l];
    		return ;
    	}
    	int mid=(l+r)/2;
    	build(k*2,l,mid);
    	build(k*2+1,mid+1,r);//思考：为什么左子树的编号是k*2,右子树的编号是k*2+1； 
    	t[k].sum=t[k*2].sum+t[k*2+1].sum;
    } //建立线段树
    void update(int k,int pos,int w){  
    	if(t[k].l==t[k].r&&t[k].l==pos){//如果当前节点是叶节点  并且当前节点等于目标位置 
    		t[k].v+=w;
    		t[k].sum+=w;
    		return ;
    	} 
    	int mid=(t[k].l+t[k].r)/2;
    	
    	if(pos<=mid) update(k*2,pos,w);//如果目标位置在左子树中 
    	if(mid<pos)  update(k*2+1,pos,w); //如果目标位置在右子树中
    	 
    	t[k].sum=t[k*2].sum+t[k*2+1].sum;//子树中的节点改变   那么相应的改变父亲节点的区间和 
    } 
    int ask(int k,int l,int r){
    	if(l<=t[k].l&&t[k].r<=r){//如果当前区间在目标区间内部 
    		return t[k].sum;
    	}
    	int mid=(t[k].l+t[k].r)/2,ans=0;
    	 
    	if(l<=mid)ans+=ask(k*2,l,r);//左子树中  包含目标区间的 点 
    	if(mid<r)ans+=ask(k*2+1,l,r);//右子树中  包含目标区间的  点 
    	return ans;
    }
    int main(){
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=n;i++)
    		scanf("%d",&d[i]);//输入数据
    		
    	build(1,1,n);//建立存放n个数据的线段树 
    	
    	for(int op,x,y,i=1;i<=m;i++){
    		scanf("%d%d%d",&op,&x,&y);
    		if(op==1){//将第x个数加上y 
    			update(1,x,y); 
    		}
    		if(op==2){
    			printf("%d\n",ask(1,x,y));
    		}
    	}
    	return 0;
    }

[2256.png]: /images/20211209/87fc665986c84a0ca0d201fbe2242b17.png