数据结构----树状数组----修改区间求点值问题

一、题目描述

给出一个N个元素的正整数序列，现在有两种操作:

1、修改操作:给一段区间的每一个数加上一个正整数x

2、查询操作:查询序列中当前第x个元素的值。

请写一个程序实现这两种操作。

输入

第一行，一个数N第二行N个数，表示初始的序列，接下来一行一个数M，表示操作次数接下来M行，每行一个操作:1.  lrx表示把l到r的每一个数加上x2. x表示查询第x个元素的值

输出

对于每一个查询操作输出一行结果

样例输入

51 1 1 1 141 2 3 22 31 1 5 32 5
样例输出
34
提示
N, M <= 100000，初始数列中每个元素不超过1000，修改操作中的x不超过1000
二、题目分析这道题目是对一个区间进行更改，对一个点进行查询。好像跟树状数组没有多大关系，因为树状数组是对一个点进行一个修改，对一个区间进行查询。但是，这道题就是用树状数组来做的。更改点值求区间时，treearray[i]表示的是i所管辖的区间的和。更改区间求点值时，treearray[i]表示的是i所管辖的区间被修改的值的和。函数的写法都是一样的，只是treearray[i]表达的意义不同，就可以产生不同的结果。但是第2个treearray[i]数组中i管辖的范围是根据getsum()函数来定的：(并不是由update来决定的)如：15是被8管辖的，15--->1111---->1000---->8，也就是highbit()。代码：
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int treearray[100005],a[100005],n;int lowbit(int x){    return x&-x;}int getsum(int x){    int sum=0;    while(x){        sum+=treearray[x];        x-=lowbit(x);    }    return sum;}void update(int x,int d){    while(x<=n){        treearray[x]+=d;        x+=lowbit(x);    }}int main(){    int i,m,l,r,d,x,o;    scanf("%d",&n);    for(i=1;i<=n;i++)        scanf("%d",&a[i]);    scanf("%d",&m);    for(i=1;i<=m;i++){        scanf("%d",&o);        if(o==1){            scanf("%d%d%d",&l,&r,&d);            update(l,d);            update(r+1,-d);        }        else{            scanf("%d",&x);            PRintf("%d/n",getsum(x)+a[x]);        }    }}