1.单点跟新单点查询
就是数组模式
2.单点更新区间查询
https://vjudge.net/problem/HDU-1166
维护一个数组c[]，c[i]表示前i进制位的和，所以更新的时候要将i以上的2进制倍数都更新；
#include<stdio.h> #include<string.h> #define N 55000 using namespace std; int c[N],n; int lowbit(int x){ return x&(-x); } void updata(int x,int k){ while(x<=n){ c[x]+=k; x+=lowbit(x); } } int sum(int x){ int sum=0; while(x){ sum+=c[x]; x-=lowbit(x); } return sum; } int main(){ int t,i,j,k; char str[10]; scanf("%d",&t); for(i=1;i<=t;i++){ scanf("%d",&n); memset(c,0,sizeof(c)); for(j=1;j<=n;j++){ scanf("%d",&k); updata(j,k); } printf("Case %d:\n",i); while(scanf("%s",str)&&strcmp(str,"End")!=0){ scanf("%d%d",&j,&k); if(!strcmp(str,"Query"))printf("%d\n",sum(k)-sum(j-1)); else if(!strcmp(str,"Add"))updata(j,k); else updata(j,-k); } } return 0; }
3.区间更新单点查询
题目中出现把x-y区间的值全部添加或者减少某个值，然后求某点的值是多少，就是用差分数组的模型。
https://www.dotcpp.com/oj/problem1501.html
#include<bits/stdc++.h> #define N 100000 using namespace std; int n,c[N+2]; int lowbit(int x){ return x&(-x); } void updata(int x,int k){ while(x<=n){ c[x]+=k; x+=lowbit(x); } } int getsum(int x){ int ans=0; while(x){ ans+=c[x]; x-=lowbit(x); } return ans; } int main(){ int m,i; int x,y,z; cin>>n>>m; for(i=1;i<=m;i++){ cin>>x>>y>>z; updata(x,z); updata(y+1,-z); } for(i=1;i<=n;i++){ cout<<getsum(i)<<" "; } return 0; }
4.区间更新区间查询
https://vjudge.net/problem/POJ-3468
十年IO一场空，不开LL见祖宗
#include<stdio.h> #include<string.h> #define N 55000 using namespace std; typedef long long LL; LL sum1[N],sum2[N],n; LL lowbit(LL x){ return x&(-x); } void updata(LL x,LL k){ int t=x; t--; while(x<=n){ sum1[x]+=k; sum2[x]+=t*k; x+=lowbit(x); } } LL sum(LL x){ LL ans=0,t=x; while(x){ ans+=t*sum1[x]-sum2[x]; x-=lowbit(x); } return ans; } int main(){ int i,m,num[N]={0}; int a,b,c; char ch; scanf("%d%d",&n,&m); for(i=1;i<=n;i++)scanf("%d",&num[i]); for(i=1;i<=n;i++)updata(i,num[i]-num[i-1]); for(i=0;i<m;i++){ getchar(); scanf("%c",&ch); if(ch==‘Q‘){ scanf("%d%d",&a,&b); printf("%lld\n",sum(b)-sum(a-1)); }else{ scanf("%d%d%d",&a,&b,&c); updata(a,c); updata(b+1,-c); } } return 0; }
原文：https://www.cnblogs.com/ydcwp/p/13919558.html