数列操作 — 线段树入门

题目

题目描述 Description

一行N个方格,开始每个格子里都有一个整数。现在动态地提出一些问题和修改:提问的形式是求某一个特定的子区间[a,b]中所有元素的和;修改的规则是指定某一个格子x,加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1≤N<100000,,提问和修改的总数m<10000条。

输入描述 Input Description

输入文件第一行为一个整数N,接下来是n行n个整数,表示格子中原来的整数。接下一个正整数m,再接下来有m行,表示m个询问,第一个整数表示询问代号,询问代号1表示增加,后面的两个数x和A表示给位置X上的数值增加A,询问代号2表示区间求和,后面两个整数表示a和b,表示要求[a,b]之间的区间和。

输出描述 Output Description

共m行,每个整数

样例输入 Sample Input

6





3
4
1 3 5
2 1 4
1 1 9
2 2 6

样例输出 Sample Output

22
22

数据范围及提示 Data Size & Hint

1≤N<100000, m<10000 。

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

思路(见代码注释)

代码

# include <cstdio>
# define N 500000		
                                       // 利用二叉树的父子节点关系来存储,因此必须保证数组开的足够大
struct node{
    int l,r,v;				// left、right、value ;左右孩子由二叉树性质计算。
};
node st[N];
int a[N];

void build(int v,int l,int r){
	st[v].l = l;
	st[v].r = r;
	if (l == r) {					// 是叶子,直接赋值,跳出
		st[v].v=a[l];
		return ;
	}
	int mid = (l+r)/2;			// 不是叶子,往下扩展
	build(2*v,l,mid);
	build(2*v+1,mid+1,r);
	st[v].v=st[v*2].v+st[v*2+1].v;	// 扩展出孩子后才能计算value域
}

void insert(int v,int w,int p){			// 在以v为根的树中,寻找节点w,并把节点w的值加上p 。 格外注意 某些编程语言中insert不能作为标识符
	if (w>=st[v].l && w<=st[v].r){	
		st[v].v += p;			// 父子之间为统治关系,凡是经过的节点都要更新value
	}
	if (st[v].l==st[v].r) return;		// 找到终点,跳出
	int mid = (st[v].l+st[v].r)/2;	
	if (w<=mid) {				// 判断左右孩子
		insert(v*2,w,p);			
	}else {
		insert(v*2+1,w,p);
	}
}

int getsum(int v,int l,int r){			// 返回以v为根节点的树中,区间 [l,r] 的value域
	if (st[v].l==l && st[v].r==r){
		return st[v].v;			// 找到,返回
	}
	int mid = (st[v].l+st[v].r)/2;
	if (r<=mid) {
		return getsum(v*2,l,r);		// 区间 [l,r] 在v的左枝上
	}else if (l>mid) {
		return getsum(v*2+1,l,r);	// 右枝
	}else {					// 兵分两路
		return getsum(v*2,l,mid) + getsum(v*2+1,mid+1,r);
	}
}

int main(void){
	freopen("1080.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,a,b;
	for (scanf("%d",&m);m;m--){
		scanf("%d%d%d",&t,&a,&b);
		if (t & 1) {
			insert(1,a,b);
		}else {
			printf("%d\n",getsum(1,a,b));
		}
	}
	return 0;
}



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

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 18:27
天津大学_2023
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议