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đ !!!