A -秋实大哥与线段树
UESTC - 1073?
“学习本无底，前进莫徬徨。” 秋实大哥对一旁玩手机的学弟说道。
秋实大哥是一个爱学习的人，今天他刚刚学习了线段树这个数据结构。
为了检验自己的掌握程度，秋实大哥给自己出了一个题，同时邀请大家一起来作。
秋实大哥的题目要求你维护一个序列，支持两种操作：一种是修改某一个元素的值；一种是询问一段区间的和。
Input
第一行包含一个整数nn，表示序列的长度。
接下来一行包含nn个整数aiai，表示序列初始的元素。
接下来一行包含一个整数mm，表示操作数。
接下来mm行，每行是以下两种操作之一：
1 x v : 表示将第x个元素的值改为v
2 l r : 表示询问[l,r]这个区间的元素和
1≤n，m，v，ai≤1000001≤n，m，v，ai≤100000，1≤l≤r≤n1≤l≤r≤n。
Output
对于每一个22 ll rr操作，输出一个整数占一行，表示对应的答案。
Sample Input
3
1 2 3
3
2 1 2
1 1 5
2 1 2
Sample Output
3
7
#include <iostream>#include <cstdio>
#define lid (id << 1)#define rid (id << 1 | 1)
using namespace std;
const int N=100005;struct node
{
int l,r;
long long sum;
}tr[N * 4];int a[N];
void push_up(int id){
tr[id].sum = tr[lid].sum + tr[rid].sum;
}
void build(int id, int l,int r){
tr[id].l = l; tr[id].r = r;
if(l == r)
{
tr[id].sum = a[l];
return;
}
int mid = (l + r) >>1;
build(lid, l, mid);
build(rid, mid +1, r);
push_up(id);
}
void updata(int id,int x,int v){
if(tr[id].l == tr[id].r){
tr[id].sum = v;
return;
}
int mid = (tr[id].l + tr[id].r) >>1;
updata(x <= mid ? lid : rid, x, v);
push_up(id);
}
long long query(int id, int l, int r){
if(tr[id].l == l && tr[id].r == r)
return tr[id].sum;
int mid = (tr[id].l + tr[id].r) >>1;
if(r <= mid) return query(lid, l, r);
if(l > mid) return query(rid, l, r);
return query(lid, l, mid)+query(rid, mid +1,r);
}
int main(){
int n,m;
int p,x,y;
scanf("%d",&n);
for(int i =1;i <= n; i ++)
scanf("%d",&a[i]);
build(1,1,n);
scanf("%d",&m);
while(m --)
{
scanf("%d%d%d",&p,&x,&y);
if(p ==1)
updata(1, x, y);
else
printf("%lld\n",query(1,x,y));
}
return 0;
}
顺便推荐一篇比较详细的讲解线段树知识点的文章。
线段树入门（一）：http://www.cnblogs.com/shadowland/p/5870339.html