click here 1。单点修改，区间查询
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int maxn=2e6+10; typedef long long ll; ll a[maxn]; int n; int lowbit(int x) { return x&(-x); } void update(int x,ll val) { for(int i=x;i<=n;i+=lowbit(i)) a[i]+=val; } ll getsum(int x) { ll res=0; for(int i=x;i>0;i-=lowbit(i)) res+=a[i]; return res; } int main() { int m; ll p; memset(a,0,sizeof a); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%lld",&p),update(i,p); while(m--) { ll t,x,y; scanf("%lld%lld%lld",&t,&x,&y); if(t==1) update(x,y); else printf("%lld\n",getsum(y)-getsum(x-1)); } return 0; }2.区间修改，单点查询 click here
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int maxn=2e6+10; int n,m; typedef long long ll; ll a[maxn]; int lowbit(int x) { return x&(-x); } void update(int x,ll val) { for(int i=x;i<=n;i+=lowbit(i)) a[i]+=val; } ll getsum(int x) { ll res=0; for(int i=x;i>0;i-=lowbit(i)) res+=a[i]; return res; } int main() { scanf("%d%d",&n,&m); ll pl=0; for(int i=1;i<=n;i++) { ll p; scanf("%lld",&p); update(i,p-pl),pl=p; } while(m--) { int x,y; ll val; int t; scanf("%d",&t); if(t==1) { scanf("%d%d%lld",&x,&y,&val); update(x,val); update(y+1,-val); } else { scanf("%d",&x); printf("%lld\n",getsum(x)); } } return 0; }3.区间修改 区间查询 click here
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int maxn=2e6+10; typedef long long ll; ll a[maxn]; ll n,m; ll s1[maxn],s2[maxn]; int lowbit(int x) { return x&(-x); } void update(int x,ll val) { for(int i=x;i<=n;i+=lowbit(i)) s1[i]+=val,s2[i]+=(x-1)*val; } ll getsum(int x) { ll res=0; for(int i=x;i>0;i-=lowbit(i)) res+=x*s1[i]-s2[i]; return res; } int main() { scanf("%lld%lld",&n,&m); ll x,p=0; for(int i=1;i<=n;i++) scanf("%lld",&x),update(i,x-p),p=x; while(m--) { int t,x,y,val; scanf("%d",&t); if(t==1) { scanf("%d%d%d",&x,&y,&val); update(x,val); update(y+1,-val); } else { scanf("%d%d",&x,&y); printf("%lld\n",getsum(y)-getsum(x-1)); } } return 0; }为什么我感觉一维比二维难qwq
