树状数组O(n)建树O(logn)修改查
2025-08-05 10:57:18
发布于:浙江
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int tr[500005];
int a[500005];
int n, m;
void build(){
for(int i = 1; i <= n; i++){
tr[i] += a[i];
if(i + (i & (-i)) <= n) tr[i + (i & (-i))] += tr[i];
}
}
void add(int idx, int val){
for(int i = idx; i <= n; i += (i & (-i))){
tr[i] += val;
}
}
int query(int idx){
int ans = 0;
for(int i = idx; i; i -= (i & (-i))){
ans += tr[i];
}
return ans;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
build();
while(m--){
int tmp;
cin >> tmp;
if(tmp == 1){
int idx, val;
cin >> idx >> val;
add(idx, val);
}else{
int l, r;
cin >> l >> r;
cout << query(r) - query(l - 1) << '\n';
}
}
return 0;
}
全部评论 8
哦日子居然会写szsz
2天前 来自 浙江
0%%%
2天前 来自 浙江
0
我是来自8888年被复活的秦始皇,我来考古
2天前 来自 浙江
0我是来自8888年被复活的秦始皇,我来考古
2天前 来自 浙江
0我是来自8888年被复活的秦始皇,我来考古
2天前 来自 浙江
0kaogu
2天前 来自 浙江
0???今天上午才发的
2天前 来自 浙江
0整整过了2.5小时
2天前 来自 浙江
0
表面考古,实际真的考古
2天前 来自 广东
0?
2天前 来自 浙江
0
d
2天前 来自 浙江
0d
2天前 来自 浙江
0
有帮助,赞一个