首页 > 代码库 > 树状数组维护区间最值
树状数组维护区间最值
在区间求和时，我们只需求出 [1, r]，[1,l?1]，利用前缀和的可减性，得到区间 [l,r] 的和。
但区间最值不满足这个性质。
我们可以把区间 [l,r] 拆分成若干个子区间，再合并得到答案。
画图可知，max_i需要的 max 只有 max_{i-2^0}, max_{i-2^1}, max_{i-2^2} ... max_{i-lowbit(i)+1}。
修改
void change(int r) {
c[r] = a[r];
for(int i = 1; i < lowbit(r); i <<= 1)
c[r] = max(c[r], c[r-i]);
}
查询
我们找 [l, r] 的最值就是子区间最值的 max，即递减 r，在这里可以有个优化，即当找到一个 max_i??，有 i?lowbit(i)≥l 时，更
新后，i = i - lowbit(i)，然后继续递减。当 l>r 就跳出循环。
int getmax(int l, int r) {
int ret = a[r];
while(l <= r) {
ret = max(ret, a[r]);
for(--r; r - l >= lowbit(r); r -= lowbit(r))
ret = max(ret, c[r]);
}
return ret;
}
需要指出的是，它只支持末端插入，不支持单点修改操作。
#include<iostream>
#include<stdio.h>
#include<memory.h>
using namespace std;
int A[200005];
int C[200005];
int lowbit(int x)
{
return x&(-x);
}
void update(int x)
{
C[x]=A[x];
for(int i=1; i<lowbit(x); i<<=1)
C[x]=max(C[x],C[x-i]);
}
int query(int l,int r)
{
int ans=A[r];
while(l<=r)
{
ans=max(ans,A[r]);
for(--r; r-l>=lowbit(r); r-=lowbit(r))
ans=max(ans,C[r]);
}
return ans;
}
int main()
{
int m,d;
scanf("%d%d",&m,&d);
int cnt = 0,t=0;
for(int i = 0; i<m; i++)
{
char op;
int n;
scanf(" %c%d",&op,&n);
if(op==‘A‘)
{
int temp = (n+t)%d;
A[++cnt]=temp;
update(cnt);
}
else
{
printf("%d\n",t = query(cnt-n+1,cnt));
}
}
return 0;
}
树状数组维护区间最值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。