算法模板
一、基础算法
1. 排序
void merge_sort(int l,int r){
if(l>=r)return;
int mid =l+r>>1;
int i=l,j=mid+1,k=0;
merge_sort(l,mid);
merge_sort(mid+1,r);
while(i<=mid&&j<=r){
if(a[i]<=a[j])b[k++]=a[i++];
else b[k++]=a[j++];
}
while(i<=mid)b[k++]=a[i++];
while(j<=r)b[k++]=a[j++];
for(int i=l,k=0;i<=r;i++,k++)a[i]=b[k];
}
void quick_sort(int l,int r){
if(l>=r)return;
int i=l-1,j=r+1,x=a[(i+j)>>1];
while(i<j){
do i++;while(a[i]<x);
do j--;while(a[j]>x);
if(i<j)swap(a[i],a[j]);
}
quick_sort(l,j);
quick_sort(j+1,r);
}
2. 二分
#include<iostream>
using namespace std;
const int N=100010;
int a[N];
int main(){
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++)cin>>a[i];
while(k--){
int x;
cin>>x;
int l=0,r=n-1;
while(l<r){
int mid=l+r>>1;
if(a[mid]>=x)r=mid;
else l=mid+1;
}
if(a[l]==x)cout<<l<<" ";
else cout<<-1<<" ";
l=0,r=n-1;
while(l<r){
int mid=l+r+1>>1;
if(a[mid]<=x)l=mid;
else r=mid-1;
}
if(a[l]==x)cout<<l<<" "<<endl;
else cout<<-1<<endl;
}
return 0;
}
3. 前缀和
#include<iostream>
using namespace std;
const int N=1010;
int a[N][N],s[N][N];
int n,m,q;
int main(){
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}
}
while(q--){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
cout<<s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]<<endl;
}
return 0;
}
4. 双指针
for(int i=0,j=0;i<n;i++){
cin>>a[i];
cnt[a[i]]++;
while(cnt[a[i]]>1){
--cnt[a[j++]];
}
ans=max(ans,i-j+1);
}
二、数据结构
1. 单调队列
#include<iostream>
using namespace std;
const int N=1000010;
int n,k;
int a[N],q[N];
int main(){
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>a[i];
}
int hh=0,tt=-1;
for(int i=0;i<n;i++){
if(hh<=tt&&i-k+1>q[hh])hh++;
while(hh<=tt&&a[q[tt]]>=a[i])tt--;
q[++tt]=i;
if(i>=k-1)cout<<a[q[hh]]<<" ";
}
puts("");
hh=0,tt=-1;
for(int i=0;i<n;i++){
if(hh<=tt&&i-k+1>q[hh])hh++;
while(hh<=tt&&a[q[tt]]<=a[i])tt--;
q[++tt]=i;
if(i>=k-1)cout<<a[q[hh]]<<" ";
}
return 0;
}
2.并查集
#include<iostream>
using namespace std;
const int N=100010;
int n,m;
int p[N];
char op[2];
int find(int x){
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)p[i]=i;
while(m--){
int x,y;
cin>>op[0]>>x>>y;
if(op[0]=='M'){
p[find(x)]=find(y);
}else{
if(find(x)!=find(y))puts("No");
else puts("Yes");
}
}
return 0;
}
3. KMP
#include<iostream>
using namespace std;
const int N=1000010;
char a[N],b[N];
int ne[N];
void get_next(char a[],int n){
for(int i=2,j=0;i<=n;i++){
while(j&&a[i]!=a[j+1])j=ne[j];
if(a[i]==a[j+1])j++;
ne[i]=j;
}
}
void kmp(char a[N],char b[N],int n,int m){
for(int i=1,j=0;i<=m;i++){
while(j&&b[i]!=a[j+1])j=ne[j];
if(b[i]==a[j+1])j++;
if(j==n){
cout<<i-n<<" ";
j=ne[j];
}
}
}
int main(){
int n,m;
cin>>n>>a+1>>m>>b+1;
get_next(a,n);
kmp(a,b,n,m);
return 0;
}
4. Trie树
#include<iostream>
using namespace std;
const int N=1e5+10;
int son[N][26],idx,cnt[N];
string s;
void insert(string str){
int p=0;
for(int i=0;i<str.size();i++){
int x=str[i]-'a';
if(!son[p][x])son[p][x]=++idx;
p=son[p][x];
}
cnt[p]++;
}
int query(string str){
int p=0;
for(int i=0;i<str.size();i++){
int x=str[i]-'a';
if(!son[p][x])return 0;
else p=son[p][x];
}
return cnt[p];
}
int main(){
int n;
cin>>n;
while(n--){
char op[2];
cin>>op>>s;
if(op[0]=='I')insert(s);
else cout<<query<<endl;
}
return 0;
}
三、图论
1. Bfs
#include<iostream>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int a[N][N],dist[N][N];
int n,m;
bool st[N][N];
queue<PII> q;
void bfs(){
q.push({1,1});
dist[1][1]=0;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
while(q.size()){
auto t=q.front();
q.pop();
for(int i=0;i<4;i++){
int xx=t.first+dx[i],yy=t.second+dy[i];
if(!st[xx][yy]&&!a[xx][yy]){
st[xx][yy]=true;
dist[xx][yy]=dist[t.first][t.second]+1;
q.push({xx,yy});
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
bfs();
cout<<dist[n][m]<<endl;
return 0;
}
2. Dfs
#include<iostream>
using namespace std;
const int N=20;
char g[N][N];
bool col[N],dg[N],udg[N];
int n;
void dfs(int u){
if(u==n){
for(int i=0;i<n;i++){
cout<<g[i]<<endl;
}
puts("");
return;
}
for(int i=0;i<n;i++){
if(!col[i]&&!dg[u+i]&&!udg[u-i+n]){
col[i]=dg[u+i]=udg[u-i+n]=true;
g[u][i]='Q';
dfs(u+1);
col[i]=dg[u+i]=udg[u-i+n]=false;
g[u][i]='.';
}
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
g[i][j]='.';
dfs(0);
return 0;
}
3. 拓扑排序
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10,M=1e6+10;
int h[N],ne[M],e[M],idx;
int n,m;
int d[N];
int q[N];
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
bool top_sort(){
int hh=0,tt=-1;
for(int i=1;i<=n;i++){
if(!d[i])q[++tt]=i;
}
while(hh<=tt){
int t=q[hh++];
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
if(--d[j]==0)q[++tt]=j;
}
}
return tt==n-1;
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
memset(d,0,sizeof d);
while(m--){
int a,b;
cin>>a>>b;
add(a,b);
d[b]++;
}
if(top_sort()){
for(int i=0;i<n;i++)cout<<q[i]<<" ";
}else cout<<-1<<endl;
return 0;
}
4. Dijsktra
#include<iostream>
#include<cstring>
using namespace std;
const int N=150010,M=1500010;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
bool st[N];
void add(int a,int b,int c){
e[idx]=b;
ne[idx]=h[a];
w[idx]=c;
h[a]=idx++;
}
int dijsktra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=1;i<=n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;
}
st[t]=true;
for(int j=h[t];~j;j=ne[j]){
int u=e[j];
dist[u]=min(dist[u],dist[t]+w[j]);
}
}
if(dist[n]==0x3f3f3f3f)return -1;
return dist[n];
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
cout<<dijsktra()<<endl;
return 0;
}
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=150010,M=1500010;
typedef pair<int ,int> PII;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
bool st[N];
void add(int a,int b,int c){
e[idx]=b;
ne[idx]=h[a];
w[idx]=c;
h[a]=idx++;
}
int dijsktra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
priority_queue<PII,vector<PII>,greater<PII>>q;
q.push({0,1});
while(q.size()){
auto [d,ver]=q.top();
q.pop();
if(st[ver])continue;
st[ver]=true;
for(int i=h[ver];~i;i=ne[i]){
int j=e[i];
if(dist[j]>d+w[i]){
dist[j]=d+w[i];
q.push({dist[j],j});
}
}
}
if(dist[n]==0x3f3f3f3f)return -1;
return dist[n];
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
cout<<dijsktra()<<endl;
return 0;
}
5.Floyd
#include<iostream>
#include<cstring>
using namespace std;
const int N=205,INF=0x3f3f3f3f;
int g[N][N];
int n,m,q;
void floyd(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
g[j][k]=min(g[j][k],g[j][i]+g[i][k]);
}
int main(){
cin>>n>>m>>q;
memset(g,0x3f,sizeof g);
for(int i=1;i<=n;i++)g[i][i]=0;
while(m--){
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(c,g[a][b]);
}
floyd();
while(q--){
int a,b;
cin>>a>>b;
if(g[a][b]>INF/2)cout<<"impossible"<<endl;
else cout<<g[a][b]<<endl;
}
return 0;
}
6.Spfa
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=100010,M=1000010;
int n,m;
int h[N],ne[M],e[M],w[M],idx;
int dist[N];
bool st[N];
void add(int a,int b,int c){
e[idx]=b;
ne[idx]=h[a];
w[idx]=c;
h[a]=idx++;
}
int spfa(){
memset(dist,0x3f,sizeof dist);
queue<int>q;
dist[1]=0;
q.push(1);
st[1]=true;
while(q.size()){
int t=q.front();
q.pop();
st[t]=false;
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
if(dist[j]>dist[t]+w[i]){
dist[j]=dist[t]+w[i];
if(!st[j]){
q.push(j);
st[j]=true;
}
}
}
}
return dist[n];
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
int ans=spfa();
if(ans!=0x3f3f3f3f)cout<<ans<<endl;
else cout<<"impossible"<<endl;
return 0;
}
7.Bellman-ford
#include<iostream>
#include<cstring>
using namespace std;
const int N=510,M=10010,inf=0x3f3f3f3f;
int n,m,k;
int dist[N],last[N];
struct Edge{
int a,b,w;
};
Edge edges[M];
void bellman_ford(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<k;i++){
memcpy(last,dist,sizeof dist);
for(int j=0;j<m;j++){
dist[edges[j].b]=min(dist[edges[j].b],last[edges[j].a]+edges[j].w);
}
}
}
int main(){
cin>>n>>m>>k;
for(int i=0;i<m;i++)cin>>edges[i].a>>edges[i].b>>edges[i].w;
bellman_ford();
if(dist[n]>inf/2)cout<<"impossible"<<endl;
else cout<<dist[n]<<endl;
return 0;
}
8.Kruskal
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10, M=2e5+10,INF=0x3f3f3f3f;
int p[N];
int n,m;
struct edge{
int a;
int b;
int w;
bool operator < (const edge &e)const{
return w<e.w;
}
}edges[M];
int find(int x){
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
int Kruscal(){
int ans=0,cnt=0;
sort(edges,edges+m);
for(int i=1;i<=n;i++)p[i]=i;
for(auto e:edges){
int a=find(e.a);
int b=find(e.b);
if(a!=b){
p[a]=b;
ans+=e.w;
cnt++;
}
}
return cnt==n-1?ans:INF;
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++)cin>>edges[i].a>>edges[i].b>>edges[i].w;
int ans=Kruscal();
if(ans==INF)cout<<"impossible"<<endl;
else cout<<ans<<endl;
return 0;
}
9.Prime
#include<iostream>
#include<cstring>
using namespace std;
const int N=550,M=100010,inf=0x3f3f3f3f;
int g[N][N];
int dist[N];
bool st[N];
int n,m;
int prime(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
int ans=0;
for(int i=1;i<=n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j]&&(t==-1||dist[j]<dist[t]))t=j;
}
st[t]=true;
if(dist[t]==inf)return inf;
ans+=dist[t];
for(int j=1;j<=n;j++)dist[j]=min(dist[j],g[t][j]);
}
return ans;
}
int main(){
memset(g,0x3f,sizeof g);
cin>>n>>m;
while(m--){
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);
}
int ans=prime();
if(ans!=inf)cout<<ans<<endl;
else cout<<"impossible"<<endl;
return 0;
}
10. 染色法
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010,M = 200010;
int h[N],ne[M],e[M],idx;
int color[N];
int n,m;
void add(int a,int b){
ne[idx] = h[a];
e[idx] = b;
h[a] = idx++;
}
bool dfs(int u,int c){
color[u] = c;
for(int i = h[u];~i;i = ne[i]){
int j = e[i];
if(!color[j]){
if(!dfs(j,3-c))return false;
}else if(color[j] == c)return false;
}
return true;
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--){
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
bool flag = true;
for(int i = 1;i <= n;i++){
if(!color[i]){
if(!dfs(i,1)){
flag = false;
break;
}
}
}
if(flag)puts("Yes");
else puts("No");
return 0;
}
11. 匈牙利算法
#include<iostream>
#include<cstring>
using namespace std;
const int N=510,M=100010;
int h[N],e[M],ne[M],idx;
int match[N];
bool st[N];
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
bool find(int x){
for(int i=h[x];~i;i=ne[i]){
int j=e[i];
if(!st[j]){
st[j]=true;
if(match[j]==0||find(match[j])){
match[j]=x;
return true;
}
}
}
return false;
}
int main(){
int n1,n2,m;
cin>>n1>>n2>>m;
memset(h,-1,sizeof h);
while(m--){
int a,b;
cin>>a>>b;
add(a,b);
}
int ans=0;
for(int i=1;i<=n1;i++){
memset(st,0,sizeof st);
if(find(i))ans++;
}
cout<<ans<<endl;
return 0;
}
四、数论
1.质数
bool isPrime(int x){
if(x<2)return false;
for(int i=2;i<=x/i;i++){
if(x%i==0)
return false;
}
return true;
}
void divided(int x){
for(int i=2;i<=x/i;i++){
if(x%i==0){
int s=0;
while(x%i==0){
x/=i;
s++;
}
cout<<i<<" "<<s<<endl;
}
}
if(x>1)cout<<x<<" "<<1<<endl;
cout<<endl;
}
#include<iostream>
#include<cstring>
using namespace std;
const int N=2000010;
int primes[N],cnt;
bool st[N];
int get_primes(int n){
for(int i=2;i<=n;i++){
if(!st[i]){
primes[cnt++]=i;
for(int j=i;j<=n;j+=i){
st[j]=true;
}
}
}
return cnt;
}
int main(){
int n;
cin>>n;
cout<<get_primes(n)<<endl;
return 0;
}
const int N=1e6+10;
int prime[N],cnt;
bool st[N];
for(int i=2;i<=n;i++){
if(!st[i])prime[cnt++]=i;
for(int j=0;prime[j]<=n/i;j++){
st[prime[j]*i]=true;
if(i%prime[j]==0)break;
}
}
2. 最大公约数
#include<iostream>
using namespace std;
int n;
int gcb(int a,int b){
return b?gcb(b,a%b):a;
}
int main(){
cin>>n;
while(n--){
int x,y;
cin>>x>>y;
cout<< gcb(x,y)<<endl;
}
return 0;
}
3. 快速幂
int qmi(LL a,LL b,LL p){
int res=1;
while(b){
if(b&1)res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
4. 组合数
#include<iostream>
using namespace std;
typedef long long LL;
const int mod=1e9+7,N=100010;
int infact[N],fact[N];
LL qmi(int a,int b,int p){
LL ans=1;
while(b){
if(b&1)ans=ans*a%p;
a=(LL)a*a%p;
b>>=1;
}
return ans;
}
int main(){
infact[0]=fact[0]=1;
for(int i=1;i<N;i++){
fact[i]=(LL)fact[i-1]*i%mod;
infact[i]=(LL)infact[i-1]*qmi(i,mod-2,mod)%mod;
}
int n;
cin>>n;
while(n--){
int a,b;
cin>>a>>b;
cout<<(LL)fact[a]*infact[b]%mod*infact[a-b]%mod<<endl;
}
return 0;
}
五、动态规划
1. 01背包
#include<iostream>
using namespace std;
const int N=1010;
int n,m;
int f[N];
int main(){
cin>>n>>m;
int v,w;
for(int i=1;i<=n;i++){
cin>>v>>w;
for(int j=m;j>=v;j--){
f[j]=max(f[j-v]+w,f[j]);
}
}
cout<<f[m]<<endl;
return 0;
}
2. 完全背包
#include<iostream>
using namespace std;
const int N=1010;
int n,m;
int f[N];
int main(){
cin>>n>>m;
int v,w;
for(int i=1;i<=n;i++){
cin>>v>>w;
for(int j=v;j<=m;j++){
f[j]=max(f[j-v]+w,f[j]);
}
}
cout<<f[m]<<endl;
return 0;
}
3. 分组背包
#include<iostream>
using namespace std;
const int N=110;
int n,m,k;
int f[N];
int v[N][N],w[N][N];
int s[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
for(int j=1;j<=s[i];j++){
cin>>v[i][j]>>w[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=m;j>=0;j--){
for(int k=0;k<=s[i];k++){
if(j>=v[i][k])f[j]=max(f[j-v[i][k]]+w[i][k],f[j]);
}
}
}
cout<<f[m]<<endl;
return 0;
}
4. 线性dp
#include<iostream>
using namespace std;
const int N=510;
int n;
int g[N][N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>g[i][j];
}
}
for(int i=n-1;i>=1;i--){
for(int j=1;j<=n;j++){
g[i][j]=max(g[i+1][j],g[i+1][j+1])+g[i][j];
}
}
cout<<g[1][1]<<endl;
return 0;
}
5. 区间dp
#include<iostream>
#include<cstring>
using namespace std;
const int N=310;
int s[N];
int f[N][N];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>s[i],s[i]+=s[i-1];
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
f[i][j]=0x3f3f3f3f;
for(int k=i;k<j;k++){
f[i][j]=min(f[i][k]+f[k+1][j]+s[j]-s[i-1],f[i][j]);
}
}
}
cout<<f[1][n]<<endl;
return 0;
}
6. 区间dp
#include<iostream>
#include<cstring>
using namespace std;
const int N=6010;
int happy[N];
int n;
bool has_par[N];
int h[N],e[N],ne[N],idx;
int f[N][2];
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void dfs(int u){
f[u][1]=happy[u];
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
dfs(j);
f[u][1]+=f[j][0];
f[u][0]+=max(f[j][1],f[j][0]);
}
}
int main(){
cin>>n;
for(int i =1;i<=n;i++){
cin>>happy[i];
}
memset(h,-1,sizeof h);
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
has_par[a]=true;
add(b,a);
}
int root=1;
while(has_par[root])root++;
dfs(root);
cout<<max(f[root][0],f[root][1])<<endl;
return 0;
}
六、复杂数据结构
1.树状数组
#include<iostream>
using namespace std;
const int N=100010;
int n,m;
int q[N],tree[N];
int lowbit(int x){
return x&(-x);
}
void add(int x,int c){
for(int i=x;i<=n;i+=lowbit(i)){
tree[i]+=c;
}
}
int query(int x){
int res=0;
for(int i=x;i;i-=lowbit(i))res+=tree[i];
return res;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%d",&q[i]);
for(int i=1;i<=n;i++)
add(i,q[i]);
while(m--){
int k,a,b;
cin>>k>>a>>b;
if(k==0){
cout<<query(b)-query(a-1)<<endl;
}else {
add(a,b);
}
}
return 0;
}
2.线段树
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
int n,m;
int w[N];//记录一下权重
struct node{
int l,r;//左右区间
int sum;//总和
}tr[N*4];//记得开 4 倍空间
void push_up(int u)//利用它的两个儿子来算一下它的当前节点信息
{
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;//左儿子 u<<1 ,右儿子 u<<1|1
}
void build(int u,int l,int r)/*第一个参数，当前节点编号，第二个参数，左边界，第三个参数，右边界*/
{
if(l==r)tr[u]={l,r,w[r]};//如果当前已经是叶节点了，那我们就直接赋值就可以了
else//否则的话，说明当前区间长度至少是 2 对吧，那么我们需要把当前区间分为左右两个区间，那先要找边界点
{
tr[u]={l,r};//这里记得赋值一下左右边界的初值
int mid=l+r>>1;//边界的话直接去计算一下 l + r 的下取整
build(u<<1,l,mid);//先递归一下左儿子
build(u<<1|1,mid+1,r);//然后递归一下右儿子
push_up(u);//做完两个儿子之后的话呢 push_up 一遍u 啊，更新一下当前节点信息
}
}
int query(int u,int l,int r)//查询的过程是从根结点开始往下找对应的一个区间
{
if(l<=tr[u].l&&tr[u].r<=r)return tr[u].sum;//如果当前区间已经完全被包含了，那么我们直接返回它的值就可以了
//否则的话我们需要去递归来算
int mid=tr[u].l+tr[u].r>>1;//计算一下我们 当前 区间的中点是多少
//先判断一下和左边有没有交集
int sum=0;//用 sum 来表示一下我们的总和
if(mid>=l)sum+=query(u<<1,l,r);//看一下我们当前区间的中点和左边有没有交集
if(r>=mid+1)//看一下我们当前区间的中点和右边有没有交集
sum+=query(u<<1|1,l,r);
return sum;
}
void modify(int u,int x,int v)//第一个参数也就是当前节点的编号,第二个参数是要修改的位置，第三个参数是要修改的值
{
if(tr[u].l==tr[u].r)tr[u].sum+=v; //如果当前已经是叶节点了，那我们就直接让他的总和加上 v 就可以了
//否则
else
{
int mid=tr[u].l+tr[u].r>>1;
//看一下 x 是在左半边还是在右半边
if(x<=mid)modify(u<<1,x,v);//如果是在左半边，那就找左儿子
else modify(u<<1|1,x,v);//如果在右半边，那就找右儿子
//更新完之后当前节点的信息就要发生变化对吧，那么我们就需要 pushup 一遍
push_up(u);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
build(1,1,n);/*第一个参数是根节点的下标，根节点是一号点，然后初始区间是 1 到 n */
//后面的话就是一些修改操作了
while(m--)
{
int k,a,b;
scanf("%d%d%d",&k,&a,&b);
if(!k)printf("%d\n",query(1,a,b));//求和的时候，也是传三个参数，第一个的话是根节点的编号 ，第二个的话是我们查询的区间
//第一个参数也就是当前节点的编号
else
modify(1,a,b);//第一个参数是根节点的下标,第二个参数是要修改的位置，第三个参数是要修改的值
}
return 0;
}
-ca9fe781c2d244deaabd5ebe8c1c61a1.JPG){kind=small}
