本文主要是介绍树状数组训练：差分应用，维护输出区间最值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
差分应用
题目链接
#include<bits/stdc++.h>using namespace std;int n, m;
const int M = 5e5 + 9;
int tree[M];void update(int x, int y) {for (int pos = x;pos <= n;pos += pos & (-pos))tree[pos] += y;
}int ask(int x) {int ans = 0;for (int pos = x;pos;pos -= pos & (-pos))ans += tree[pos];return ans;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m;int c;int last = 0;//构造差分树for (int i = 1;i <= n;i++)cin >> c, update(i, c - last), last = c;while (m--) {int a;cin >> a;if (a == 1) {int x, y, k;cin >> x >> y >> k;update(x, k);update(y + 1, -k);}else if (a == 2) {int z;cin >> z;cout << ask(z) << '\n';}}return 0;
}
维护区间最值
题目链接
#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<cstdlib>#include<algorithm>#include<queue>#define ll long long#define re register#define il inline#define fp(i,a,b) for(re int i=a;i<=b;i++)#define fq(i,a,b) for(re int i=a;i>=b;i--)using namespace std;const int N=50005; int n,q,c[N],b[N],s[N]; //b维护最大值，s维护最小值il int gi(){re int x=0,t=1;re char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();if(ch=='-') t=-1,ch=getchar();while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*t;}il void add(re int x,re int k)//区间维护最大最小值{for(;x<=n;x+=x&-x) b[x]=max(b[x],k),s[x]=min(s[x],k);}il int Query(re int l,re int r)//区间查询最大最小值{re int mn=2e9,mx=-1;while(l<=r){for(;r-(r&-r)>=l;r-=r&-r) mx=max(mx,b[r]),mn=min(mn,s[r]);mx=max(c[r],mx);mn=min(mn,c[r]);r--;//还有一部分区间未涉及}return mx-mn;}int main(){memset(s,63,sizeof(s));n=gi();q=gi();fp(i,1,n){c[i]=gi();add(i,c[i]);}fp(i,1,q) {re int l=gi(),r=gi();printf("%d\n",Query(l,r));}return 0;
}
这篇关于树状数组训练：差分应用，维护输出区间最值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
