首页 > 代码库 > 线段树
线段树
直接上题吧，半写半抄的题解
新大陆signed；
洛谷3372
https://www.luogu.org/problem/show?pid=3372
如题，已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数加上x
2.求出某区间每一个数的和
输入格式：
第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k
操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和
输出格式：
输出包含若干行整数，即为所有操作2的结果。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 //========================================== 6 struct NODE{ 7 int left,right,sum; 8 int lazey; 9 }tree[300005]; 10 //========================================== 11 int a[100005],f[100005]; 12 int N,M; 13 //========================================== 14 void init(); 15 void build(int ,int ,int ); 16 void work(); 17 void updata(int ,int ,int ,int); 18 int query(int ,int,int ); 19 void pushdown(int rt); 20 //========================================== 21 void pushdown(int rt) 22 { 23 int mid=( tree[rt].left + tree[rt].right )>>1; 24 tree[rt<<1].sum+=( mid - tree[rt].left + 1 )*tree[rt].lazey; 25 tree[(rt<<1)+1].sum+=( tree[rt].right - mid )*tree[rt].lazey; 26 tree[rt<<1].lazey+=tree[rt].lazey; 27 tree[(rt<<1)+1].lazey+=tree[rt].lazey; 28 tree[rt].lazey=0; 29 } 30 //========================================== 31 void updata(int rt,int left,int right,int k) 32 { 33 if( left<=tree[rt].left && tree[rt].right<=right ){ //全包含 34 tree[rt].sum+=( tree[rt].right-tree[rt].left+1 )*k; 35 tree[rt].lazey+=k; 36 return; 37 } 38 if( right<tree[rt].left || tree[rt].right <left ){ //全不包含 39 return; 40 } 41 if( tree[rt].lazey )pushdown(rt); 42 updata( rt<<1 , left ,right , k ); 43 updata( (rt<<1)+1 , left , right ,k ); 44 tree[rt].sum=tree[rt<<1].sum+tree[(rt<<1)+1].sum; 45 } 46 //========================================== 47 int query(int rt,int left,int right) 48 { 49 if( left<=tree[rt].left && tree[rt].right<=right ){ 50 return tree[rt].sum; 51 } 52 if(right<tree[rt].left || tree[rt].right <left){ 53 return 0; 54 } 55 if( tree[rt].lazey )pushdown(rt); 56 return query( rt<<1 , left , right )+query( (rt<<1)+1 , left ,right ); 57 } 58 //========================================== 59 void build(int rt,int left,int right) 60 { 61 tree[rt].left=left; 62 tree[rt].right=right; 63 tree[rt].lazey=0; 64 if( left == right ){ 65 tree[rt].sum=a[left]; 66 return; 67 } 68 build( rt<<1 , left , (left+right)>>1 ); 69 build( (rt<<1)+1 , ((left+right)>>1)+1 , right ); 70 tree[rt].sum=tree[rt<<1].sum+tree[(rt<<1)+1].sum; 71 } 72 //========================================== 73 void work() 74 { 75 int xx,yy,zz,kk; 76 for(int i=1;i<=M;i++){ 77 scanf("%d%d%d*c",&xx,&yy,&zz); 78 if(xx==1){ 79 scanf("%d*c",&kk); 80 updata(1, yy , zz , kk ); 81 } 82 else{ 83 printf("%d\n",query( 1 , yy , zz )); 84 } 85 } 86 } 87 //========================================== 88 void init() 89 { 90 scanf("%d%d*c",&N,&M); 91 for(int i=1;i<=N;i++){ 92 scanf("%d*c",&a[i]); 93 } 94 } 95 //========================================== 96 int main() 97 { 98 init(); 99 build(1,1,N);100 work();101 return 0;102 }
线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。