25121. Tổng Đoạn Con

Mã bài: BIT01

Cho dãy số có N phần tử và Q truy vấn có dạng:

1 i v: Gán a[i] = v (1 ≤ i ≤ N; |v| ≤ 109).

2 l r: Tính tổng a[l] + a[l + 1] + ... + a[r - 1] + a[r] (1 ≤ l ≤ r ≤ N).

Input

Dòng 1 chứa số nguyên N và Q (1 ≤ N, Q ≤ 105).

Dòng 2 chứa N số biểu diễn dãy a (|a[i]| ≤ 109).

Dòng 3..Q+2: Mỗi dòng chứa một truy vấn.

Output

Kết quả của mỗi truy vấn 2.

Example

Input:

4 3
1 2 3 4
2 1 4
1 1 5
2 1 4

Output:

10
14

em làm như sau 

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn=1e5+100;
#define For(i,a,b) for(int i=(a),b_=(b);i<b_;++i)
#define Ford(i,a,b) for(int i=(a),b_=(b);i>=b_;--i)

ll a[maxn],kq[maxn];
ll t[4*maxn+5];
ll n,q,m1,h,l,r;
//******************************
void up(ll x){
  for(; x<= n; x += x & -x) t[x] += m1;
}
//**********************************
ll tt(ll x){
  ll to=0;
 for(; x>0;  x -=x & -x) to+= t[x];
  return to;
}
//**********************************
int main (){
   // freopen("xx.inp","r",stdin);
   // freopen("yy.out","w",stdout);
   // ios_base::sync_with_stdio(false);
    memset(t,0,sizeof t);
    cin>>n>>q;
    For(i,1,n+1) {cin>>a[i];  m1=a[i];  up(i);  }
    ll d=0;
    For(i,0,q){
        cin>>h>>l>>r;
        m1=r-a[l];
        if(h==1) up(l);
        else { kq[d++]=tt(r)-tt(l-1); }
    }
    For(i,0,d-1) cout<<kq[i]<<endl;
    cout<<kq[d-1];
    return 0;
}

nộp dc 0đ !!!