离散化
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=3e5+9;
ll a[N];
struct Q
{ll a,b;
}Add[N],Que[N];//用结构体存储数值对
vector<ll>X;
ll getIdx(ll x)//得到离散化数组下标
{return lower_bound(X.begin(),X.end(),x)-X.begin()+1;//二分找到x的下标+1使它的下标从1开始，便于后边的计算
}
int main()
{ll n,q;cin>>n>>q;for(int i=1;i<=n;i++){ll x,w;cin>>x>>w;X.push_back(x);Add[i]={x,w};}for(int i=1;i<=q;i++){ll l,r;cin>>l>>r;X.push_back(l);X.push_back(r);Que[i]={l,r};}//排序去重sort(X.begin(),X.end());X.erase(unique(X.begin(),X.end()),X.end());for(int i=1;i<=n;i++){ll x=getIdx(Add[i].a);ll w=Add[i].b;a[x]+=w;}for(int i=1;i<=X.size();i++)a[i]+=a[i-1];//计算离散化数组的前缀和for(int i=1;i<=q;i++)//q次查询{ll l=getIdx(Que[i].a);ll r=getIdx(Que[i].b);cout<<a[r]-a[l-1]<<'\n';}return 0;
}树状数组
单点修改
#include<bits/stdc++.h>
using namespace std;
using ll=long long ;
const int N=2e5+9;
ll a[N],t[N];
ll n,q;
int lowbit(int x)//函数用于计算一个整数 x 的二进制表示中最低位的 1 所对应的值。例如，对于 x = 6（二进制表示为 110），lowbit(6) 的结果为 2（二进制表示为 10）
{return x & -x;
}
void update(int k,ll v)//函数用于将第 k 个元素的值增加 v。通过不断更新包含第 k 个元素的树状数组节点，保证树状数组的正确性
{for(int i=k;i<=n;i+=lowbit(i))t[i]+=v;
}
ll getsum(int k)//函数用于计算前 k 个元素的和。通过不断累加包含前 k 个元素的树状数组节点的值，得到最终的和
{ll res=0;for(int i=k;i>0;i-=lowbit(i))res+=t[i];return res;
}
int main()
{cin>>n>>q;for(int i=1;i<=n;i++)cin>>a[i];//构造树状数组for(int i=1;i<=n;i++)update(i,a[i]);while(q--){int op;cin>>op;if(op==1){int k;cin>>k;ll v;cin>>v;update(k,v);}if(op==2){int l,r;cin>>l>>r;cout<<getsum(r)-getsum(l-1)<<'\n';}}return 0;
}区间修改
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=3e5+9;
ll a[N],td[N],tid[N];
ll n,q;
int lowbit(int x)
{return x&-x;
}
void update(int k,ll v)
//update 函数用于更新树状数组。当对数组中某个位置 k 进行修改时，需要更新 td 和 tid 两个树状数组。具体来说，td[i] 记录的是差分数组在对应位置的累加和，tid[i] 记录的是差分数组乘以位置的累加和。通过不断更新包含位置 k 的树状数组节点，保证树状数组的正确性
{for(int i=k;i<=n;i+=lowbit(i))td[i]+=v,tid[i]+=k*v;
}
ll getsum(int k)
//getsum 函数用于计算前缀和。通过累加包含前 k 个元素的树状数组节点的值，得到最终的前缀和。这里的公式 (k + 1) * td[i] - tid[i] 是根据差分数组的性质推导出来的，用于将差分数组转换为原数组的前缀和。
{ll ans=0;for(int i=k;i>0;i-=lowbit(i))ans+=(k+1)*td[i]-tid[i];return ans;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>q;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)update(i,a[i]),update(i+1,-a[i]);while(q--){int op;cin>>op;if(op==1){ll l,r,v;cin>>l>>r>>v;update(l,v),update(r+1,-v);}else{ll l,r;cin>>l>>r;cout<<getsum(r)-getsum(l-1)<<'\n';}}return 0;
}
