~~为什么要简单问题复杂化~~
by ssilrrr @ 2022-01-27 19:09:19
你用的是线段树？
应该用树状数组，先提供一下我的代码，不要抄，看会了自己写
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,tree[2000010];
int lowbit(int x){
return x&-x;
}
void add(int x,int k){
for(;x<=n;x+=lowbit(x)) tree[x]+=k;
}
int ask(int x){
int ans=0;
for(;x;x-=lowbit(x)) ans+=tree[x];
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int a;
cin>>a;
add(i,a);
}
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
if(a==1) add(b,c);
if(a==2) cout<<ask(c)-ask(b-1)<<endl;
}
return 0;
}
```
by At_sunrise @ 2022-01-27 23:11:50
@[无名黑客](/user/499391)
1. 本题可以用线段树过去，代码如下：
```
#include <iostream>
using namespace std;
const int N = 5e5 + 10;
int w[N], n, m;
struct Tree
{
int l, r;
int sum;
}tr[N * 4];
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r)
{
tr[u] = {l, r};
if (l == r)
{
tr[u].sum = w[r];
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void modify(int u, int x, int v)
{
if (tr[u].l == tr[u].r && tr[u].l == x)
{
tr[u].sum += v;
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
if (x > mid) modify(u << 1 | 1, x, v);
pushup(u);
}
int query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
int mid = tr[u].l + tr[u].r >> 1;
int res = 0;
if (l <= mid) res = query(u << 1, l, r);
if (r > mid) res += query(u << 1 | 1, l, r);
return res;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++ ) cin >> w[i];
build(1, 1, n);
while(m -- ) {
int qwq, x, y;
cin >> qwq >> x >> y;
if(qwq == 1) modify(1, x, y);
else cout << query(1, x, y) << endl;
}
return 0;
}
```
2. 我写的是fhq-treap（无旋treap），不是线段树！！
by Link_Cut_Y @ 2022-03-13 11:27:21