一、題目描述

給出一個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]);        }    }}