区间插入求和 — 线段树入门(二)

题目

题目描述 Description

给你N个数,有两种操作:
1:给区间[a,b]的所有数增加X
2:询问区间[a,b]的数的和。

输入描述 Input Description

第一行一个正整数n,接下来n行n个整数,再接下来一个正整数Q,每行表示操作的个数,如果第一个数是1,后接3个正整数,表示在区间[a,b]内每个数增加X,如果是2,表示操作2询问区间[a,b]的和是多少。

输出描述 Output Description

对于每个询问输出一行一个答案

样例输入 Sample Input

3
1
2
3
2
1 2 3 2
2 2 3

样例输出 Sample Output

9

数据范围及提示 Data Size & Hint

1<=n<=200000
1<=q<=200000

地址:http://wikioi.com/problem/1082/

思路(见代码注释)

代码

# include <cstdio>
# include <iostream>
# define N 5000000
using namespace std;
struct node{
	int l,r;
	long long sum,inc;		// sum记录以该节点为根的树的和,inc表示该节点所统治的每个叶子节点都增加的值
};
node st[N];
int a[N];

void build(int v,int l,int r){		// 本段代码 同 数列操作1
	st[v].l=l;
	st[v].r=r;
	if (st[v].l==st[v].r){
        st[v].sum=a[l];
        return ;
	}
	int mid = (l+r)/2;
    build(v*2,l,mid);
    build(v*2+1,mid+1,r);
    st[v].sum=st[v*2].sum + st[v*2+1].sum;
}

void insert(int v,int l,int r,long long c){          // 插入
	st[v].sum+=c*(r-l+1);				
	if (l==st[v].l && r==st[v].r){	                // 如果正好需要这段,更新inc值,跳出
		st[v].inc+=c;
		return ;
	}
	int mid = (st[v].l+st[v].r)/2;                  // 向下更新
	if (r<=mid) insert(v*2,l,r,c);
	else if (l>mid) insert(v*2+1,l,r,c);
	else {
		insert(v*2,l,mid,c);
		insert(v*2+1,mid+1,r,c);
	}
}

long long getsum(int v,int l,int r){							// 求和
	if (l==st[v].l && r==st[v].r) return st[v].sum;				// 找到,返回
	int mid = (st[v].l + st[v].r)/2;
	if (r<=mid) return getsum(v*2,l,r) + st[v].inc*(r-l+1);		// 如果还需要向下寻找,回溯的时候务必加上 该节点的inc值
	else if (l>mid) return getsum(v*2+1,l,r) + st[v].inc*(r-l+1);
	else return getsum(v*2,l,mid) + getsum(v*2+1,mid+1,r) + st[v].inc*(r-l+1);
}

int main(){
	freopen("1082.in","r",stdin);
	int n;
	scanf("%d",&n);
	for (int i(1);i<=n;i++) {
		scanf("%d",&a[i]);
	}
	build(1,1,n);
	int m,t,l,r,c;
	for (scanf("%d",&m);m;m--){
		scanf("%d%d%d",&t,&l,&r);
		if (t & 1){
			scanf("%d",&c);
			insert(1,l,r,c);
		}else {
			//printf("%d\n",getsum(1,l,r));
			cout << getsum(1,l,r) << endl;
		}
	}
	return 0;
}


注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-20 17:21
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-16 02:48
门头沟学院_2022
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议