### SEI说树状数组不能处理区间最值?

### SEI说树状数组不能处理区间最值?,第1张

### SEI说树状数组不能处理区间最值?

众所周知,普通的树状数组处理区间和,都是运用容斥原理来完成运算的

但是,区间最值无法运用容斥原理来求,这怎么办呢?


### 不过,这就是很多人没有看到树状数组的本质了

我们来分析一下树状数组的节点:

f(1) for a(1)

f(2) for f(1)+a(2) = a(1)+a(2)

f(3) for a(3)

f(4) for f(2)+f(3)+f(4) = f(1~4)

f(5) ......

其中‘+’加号不一定是加法,也可用乘法,max,min等代替。

## 那么,我们可以发现什么?

对于f(x),它管辖的是(x-lowbit(x)+1)~x的所有元素,这也是树状数组最基本的定义。

也就是说,对于数x,我们求其的前缀和,就如同把其倍增地二进制分解为约莫log2(x)颗根节点范围为2^k的线段树,其中k为非负整数。

也就是倍增与分块。

那么,区间最值如何查询呢?

我们看到,由于前缀和是从1求起的,正好符合自然数的规律,所以分解为了多个2的非负整数次方的和。

那如果我们不让它从1求起呢?

当我们写树状数组时,经常会写到这种形式:

```cpp
......

int query(int x){
    int sum=0;
    while(x)
        sum+=t[x],x-=lowbit(x);
    return sum;
}

......
```


其中while循环与每次结束后的x-lowbit(x)等价于:

```cpp
for(;x>=1;x-=lowbit(x))
```

由于是前缀和,所以x>=1。

不难发现如果从下标2求起就是x>=2,从5求起就是x>=5,其中边界细节需要微调。

那么思路就很清晰了,如果求l~r区间的最值,循环即为(;r>=l;r-=lowbit(r)),其中一部分遍历到l之前,可以暂时不用树状数组,一格一格跳,等到遍历到管辖范围稍小的节点再用t[x]求值。

即:
```cpp
int query(int a,int b){
    int sum=-INF;
    while(b>=a){
        sum=max(sum,f[b]),--b;
        for(;b-lowbit(b)>=a;b-=lowbit(b))
            sum=max(sum,t[b]);
    }
    return sum;
}
```

很优秀,时间复杂度最劣也不到2log2(r-l+1)。

但是对于[P1886](https://www.luogu.com.cn/problem/solution/P1886)单调队列这题的魔鬼数据还是会跪下,怎么办呢?

引进一个小优化,另sum数组:

```cpp
sum[i]=max(sum[i-1],a[i])
```

容易发现当sum[r]>sum[r-l]时,sum[r]即为l~r区间,也是所有数组下标<=r的元素中的最大值

我也不知道为什么,这个小优化省下了大量的时间。

本题AC代码如下:

```cpp
#include
#include
using namespace std;
const int maxn=1000001,INF=1145141919;
inline int read(){
    int x=0,f=1; char ch=getchar();
    while(ch<48||ch>57){if(ch=='-'){f=-1;}ch=getchar();}
    while(ch>=48&&ch<=57){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
    return x*f;
}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a int n,m,k,l,r,f[maxn],t[maxn],f1[maxn],t1[maxn],s[maxn],s1[maxn];
int lowbit(int x){return x&-x;}
void update(int pos){
    while(pos<=n){
        t[pos]=f[pos],t1[pos]=f1[pos];
        for(int i=1;i             t[pos]=max(t[pos],t[pos-i]),t1[pos]=min(t1[pos],t1[pos-i]);
        pos+=lowbit(pos);
    }
}
int query(int a,int b){
    int sum=-INF;
    while(b>=a){
        sum=max(sum,f[b]),--b;
        for(;b-lowbit(b)>=a;b-=lowbit(b))
            sum=max(sum,t[b]);
    }
    return sum;
}
int query1(int a,int b){
    int sum=INF;
    while(b>=a){
        sum=min(sum,f1[b]),--b;
        for(;b-lowbit(b)>=a;b-=lowbit(b))
            sum=min(sum,t1[b]);
    }
    return sum;
}
int main()
{
    n=read(),k=read();
    for(int i=1;i<=n;++i)
        t1[i]=INF,t[i]=-INF;
    s[0]=INF,s1[0]=-INF;
    for(int i=1;i<=n;++i)
    {
        f[i]=f1[i]=read(),s[i]=min(s[i-1],f[i]),s1[i]=max(s1[i-1],f[i]);
        update(i);
    }
    for(int i=k;i<=n;++i)
        printf("%d ",s[i]!=s[i-k]?s[i]:query1(i-k+1,i));
    putchar(10);
    for(int i=k;i<=n;++i)
        printf("%d ",s1[i]!=s1[i-k]?s1[i]:query(i-k+1,i));
    return 0;
}
```


[P3865 ST表](https://www.luogu.com.cn/problem/P3865)同理。

第二篇题解,文章何处有误请见谅,望指正。

欢迎分享,转载请注明来源:内存溢出

原文地址:https://outofmemory.cn/langs/3002965.html

(0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
上一篇 2022-09-27
下一篇2022-09-27

随机推荐

  • 公主与郡主的区别

    公主一般指的是古代皇帝的女儿,而郡主则是其他皇室宗亲的女儿,在地位上,郡主要远比公主低的多。在古代,并非只有皇帝的女儿才能被称为公主,像是亲王的女儿,或是被派出去和亲的人也是可以被破例封为公主的。

    2022-12-06
    000
  • 唐代宗合葬的皇后是

    唐代宗总共有两个皇后,但是这两个皇后都没有能够跟他合葬。唐代宗死后被葬在了元陵,他生前最宠爱的独孤贵妃死后被追谥为贞懿皇后,贞懿皇后被葬在了庄陵之园。而唐代宗的另外一个皇后睿真皇后沈氏,因为在安史之

    2022-12-06
    000
  • 辛者库是干什么的

    清宫剧中时常会见到宫女因犯事被罚入辛者库,辛者库做的都是体力活,最脏的活,像什么洗衣服、刷马桶等,被罚入辛者库的人,干活是又辛苦又累,有时还挨打,吃不饱。辛者

  • 岳飞是哪个朝代的人

     岳飞是宋朝人,在大家的心中有名的大功臣,虽然在战争上面他有着非常大的成就,但是也因为他的战功累累,最后被奸臣秦桧害死。我们所熟知的岳飞是抗金名将,中国历史上非常名军事家、战略家,位列南宋中兴四将之首

    2022-12-06
    000
  • 舞狮子的由来

     舞狮起源于汉朝时狮子第一次从西域传入,有人模仿狮子的外貌和动作制作成了戏剧,到三国时发展成舞狮。舞狮作为一项民间艺术,在逢年过节或者举行庆典的时候,人们会舞狮助兴。伴随着锣鼓声,表演者们会穿上用红、

    2022-12-06
    000
  • 半路杀出个程咬金的经过是怎样的

    程咬金,是唐朝开国大将,也是凌烟阁二十四功臣之一。在小说《说唐演义全传》中,程咬金听说靠山王杨林要派两位太保将48万两银子送到京城长安,便打算打劫他们。送银子当日,程咬金和手下隐蔽了起来。等队伍到达大

    2022-12-06
    000
  • 水上飞机是怎么起飞的

    导语:通常情况下,我们看到的场景是飞机在机场跑道上起飞,认为只有平坦的地面,才能帮助飞机完成起飞的操作。最近有些对飞机感兴趣的朋友好奇,飞机能在水面上起飞吗?飞机可以在水面起飞吗?今天就来给大家强行分

    2022-12-06
    000
  • 形容声音的aabb式词语有哪些

    1、呼呼啦啦。亦作“呼喇喇”。象声词。多形容风声、流水声、鸟振翅声等。2、轰轰隆隆。象声词。形容雷声、炮声、爆炸声、机器声等。3、淅淅沥沥。形容轻微的风雨声、落叶声等。4、哗哗拉拉。亦作“哗啦啦”。亦

    2022-12-06
    000
  • 关于acca的介绍是什么

    ACCA是特许公认会计师公会,它是英国具有特许头衔的4家注册会计师协会之一,也是当今最知名的国际性会计师组织之一。ACCA资格被认为是"国际财会界的通行证"。许多国家立法许可ACCA会员从事审计、投资

    2022-12-06
    000

发表评论

登录后才能评论

评论列表(0条)

    保存