[codevs 1080] 선분 트 리 연습 (단점 수정 + 구간 과)

제목 설명 한 줄 에 N 개의 격자 가 있 고 모든 칸 에 정수 가 있 습 니 다.현재 동태 적 으로 몇 가지 문제 와 수정 을 제기 합 니 다. 질문 의 형식 은 특정한 하위 구간 [a, b] 중의 모든 요소 의 합 을 구 하 는 것 입 니 다.수 정 된 규칙 은 특정한 칸 x 를 지정 하고 특정한 값 A 를 추가 하거나 빼 는 것 이다.지금 은 모든 질문 에 정확 한 대답 을 할 수 있 도록 요구한다.1 ≤ N < 100000, 질문 및 수 정 된 총 m < 10000 개.
입력 설명 Input Description 입력 파일 의 첫 번 째 행동 의 정수 N 을 입력 하 십시오. 다음은 n 줄 n 개의 정수 입 니 다. 칸 의 원래 정 수 를 표시 합 니 다.다음 정수 m 를 이 어 m 줄 이 있다. m 개의 질문 을 나타 낸다. 첫 번 째 정 수 는 문의 번 호 를 나타 내 고 문의 번 호 는 1 이 증가 하 는 것 을 나타 내 며 뒤의 두 개의 수 x 와 A 는 위치 X 에 있 는 수치 에 A 를 증가 하 는 것 을 나타 낸다. 문의 번 호 는 구간 구 화 를 나타 내 고 뒤의 두 정 수 는 a 와 b 를 나타 내 며 [a, b] 간 의 구간 과 를 요구한다.
출력 설명 출력 설명
샘플 입력 Sample Input 6
4
5
6
2
1
3
4
1 3 5
2 1 4
1 1 9
2 2 6
샘플 출력 샘플 출력 22
22
데이터 범위 및 제시 Data Size & Hint 1 ≤ N ≤ 100000, m ≤ 10000.

#include
#include
#include
#include
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define sz(x) (tree[x].r-tree[x].l+1)
#define ll long long
using namespace std;
const ll maxn=200000+5;
ll num[maxn];
ll n,m;
struct edge
{
    ll l,r;
    ll add,sum;
}tree[maxn<<2];
void update(ll p)
{
    tree[p].sum=tree[L(p)].sum+tree[R(p)].sum;
    return;
}
void spread(ll p)
{
    if(!tree[p].add) return;
    tree[L(p)].add+=tree[p].add;
    tree[R(p)].add+=tree[p].add;
    tree[L(p)].sum+=tree[p].add*sz(L(p));
    tree[R(p)].sum+=tree[p].add*sz(R(p));
    tree[p].add=0;
    update(p);
    return;
}
void build(ll l,ll r,ll p)
{
    tree[p].l=l,tree[p].r=r;
    if(l==r)
    {
        tree[p].sum=num[l];
        return;
    }
    ll mid=(tree[p].l+tree[p].r)>>1;
    build(l,mid,L(p));
    build(mid+1,r,R(p));
    update(p);
    return;
}
/*void change(ll l,ll r,ll p,ll v)
{
    if(l<=tree[p].l&&tree[p].r<=r)
    {
        tree[p].add+=v;
        tree[p].sum+=v*sz(p);
        return;
    }
    spread(p);
    ll mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid) change(l,r,L(p),v);
    if(r>mid) change(l,r,R(p),v);
    update(p);
    return;
}
*/
void change(ll w,ll v,ll p)
{
    if(tree[p].l==tree[p].r)
    {
        //tree[p].add+=v;
        tree[p].sum+=v;
        return;
    }
    spread(p);
    ll mid=(tree[p].l+tree[p].r)>>1;
    if(w<=mid) change(w,v,L(p));
    else change(w,v,R(p));
    update(p);
    return;
}
ll ask_sum(ll l,ll r,ll p)
{
    if(l<=tree[p].l&&tree[p].r<=r)
    {
        return tree[p].sum;
    }
    spread(p);
    ll ans=0,mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid) ans+=ask_sum(l,r,L(p));
    if(r>mid) ans+=ask_sum(l,r,R(p));
    return ans;
}
ll t,a,b;
int main()
{
    scanf("%lld",&n);
    memset(num,0,sizeof(num));
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&num[i]);
    }
    build(1,n,1);
    scanf("%lld",&m);
    while(m--)
    {
        scanf("%lld%lld%lld",&t,&a,&b);
        if(t==1)
        {
            change(a,b,1);
        }
        else if(t==2)
        {
            cout<1)<<'
';
        }
    }
    return 0;
}