[模板]树状数组(区间修改单点查询)

Important

Bit is a good alogrithm.

Problem

Description

Give you some operate.

0 l r w   :fl..r+=w

1 x        :Ask fx

Sample:

Input:
10 10
0 2 8 5
1 7
1 2
0 3 9 8
1 7
1 3
1 5
1 5
0 1 5 6
1 2
Output:
5
5
13
13
13
13
11

Constraints

Data	n	m
1..3	103	103
4..10	105	105

Solution

0:

add(l,w);
add(r+1,-w);

1:

query(x);

Code

int bit[100010],n,t,l,r,h;
void add(int x,int y)
{
    while(x<=n)
    {
        bit[x]+=y;
        x+=x&(-x);
    }
}
int query(int x)
{
    int r=0;
    while(x)
    {
        r+=bit[x];
        x-=x&(-x);
    }
    rt r;
}
int main(){
    n=read();
    t=read();
    while(t--)
        if(!read())
        {
            l=read(),r=read(),h=read();
            add(l,h);
            add(r+1,-h);
        }
        else
            printf("%d\n",query(read()));
    rt 0;
}