神犇求解…树状数组能求区间最值吗?时间复杂度是多少啊?…还有就是树状...

发布网友发布时间：2022-04-24 20:53

共2个回答

热心网友时间：2022-04-12 20:20

其实树状数组是可以求区间最值的。区间最值问题一般称作RMQ问题，有树状数组算法，S-T算法，以及线段树算法。对于树状数组，修改的复杂度都是O（nlogn），查询是O（logn）其优势相对于线段树，代码风格整齐，简短，相对于S-T，可以进行修改，是一种比较好用的数据结构。
void modify(int p,int v){
for(int i=p;i<=N;i++){
for(int j=i;j<=N;j+=lowbit(j)){
idx[i]=max(idx[i],seq[i]);
}
}
}

int query(int l,int r){
int ans=seq[r];
while(1){
ans=max(ans,seq[r]);
if(l==r) break;
for(r-=1;r-l>=lowbit(r);r-=lowbit(r)){
ans=max(ans,idx[r]);
}
}
return ans;
}
seq[]是数列，idx[]为索引数组，维护的是一段区间内的最大值。

热心网友时间：2022-04-12 21:38

树状数组是用来算静态序列区间子段和的，不能用来求最值，静态序列求区间最值得话应该用Rmq，与此相关的算法还有线段树（这个前面说的都能求，而且可以动态维护）。追问额……那么请问树状数组在求解什么问题上更有优势？只有求前缀和吗？

追答就我看来，树状数组除了代码短，常数小，没别的优势了，基本上能用树状数组的一定能用线段树。