树状数组求区间最值

闲谈一下

树状数组最基本的功能是加速前缀和的更新。

查询一个数组的前缀和本来是O(1)的复杂度，用树状数组则为O(logn)。
但树状数组优点在于单点更新时复杂度为O(logn)，而正常的为O(n)，这也就使得树状数组能够进行大规模的更新。
虽然查询速度(O(logn))稍有些慢(相对于O(1)而言)，但依旧可以用于大规模的查询。

总之，遇到有不断更新的数组前缀和时可以考虑树状数组。

树状数组求区间最值

就像线段树一样，我们一开始接触线段树时一般也是求区间和，学会以后发现仅仅需要将sum改成max就能求出区间最值，既然可以将树状数组理解为线段树的单点更新版本，那树状数组又如何呢？

事实上，树状数组也仅需要作出少许修改即可实现单点更新+区间查询求最值。
（如果只需要前缀最值那么就真的只需要将修改及查询操作中的 $+$+号改为 $max/min$max/min，极为简洁）

单点更新

在最值的单点更新时，不像前缀和的单点更新那样仅仅需要考虑当前点修改以后会对后面的的数产生什么影响。

而需要额外考虑的是当前点的修改究竟由什么决定。

前缀和只需要给定一个增量(不是末状态)，然后即可对x处(以及后面所有的x+lowbit(x)处)进行修改。

但对于区间最值而言，b[x]数组表示[x-lowbit(x)+1, x]这个区间的最值，因此不知道x处（以及后面所有的x+lowbit(x)处）在改变时的增量是多少。想得到x处的末状态只能通过与这个区间的所有值再进行一个求最值。

是不是一眼看上去复杂度有点高？仅仅单点更新就到达了nlogn了。

但值得庆幸的是，既然是树状数组，那一定有她特色的地方

可以发现：在x处求末状态时，对它能产生影响的究竟有哪些点？肯定不是[x-lowbit(x)+1, x]这整个区间。

有影响的只有： $x\left(a\right[x\left]\right),x-2^0,x-2^1,x-2^2,\dots ,x-2^k(k满足2^k\&lt;lowbit(x\left)\right)。$x(a[x]),x−20,x−21,x−22,…,x−2k(k满足2k<lowbit(x))。
举例：
若 $x=10010000$x=10010000

$=10001000+lowbit\left(10001000\right)=10001000+1000=10001000+2^3$=10001000+lowbit(10001000)=10001000+1000=10001000+23

$=10001100+lowbit\left(10001100\right)=10001100+100=10001100+2^2$=10001100+lowbit(10001100)=10001100+100=10001100+22

$=10001110+lowbit\left(10001110\right)=10001110+10=10001110+2^1$=10001110+lowbit(10001110)=10001110+10=10001110+21

$=10001111+lowbit\left(10001111\right)=10001111+1=10001111+2^0$=10001111+lowbit(10001111)=10001111+1=10001111+20

因此要更新x处的b[x]值，复杂度仅为logn，再加上x后续的一堆x+lowbit(x)，总复杂度为logn*logn=(logn)²。

到现在为止，我们可以得到简洁的单点更新代码了：

void updata(int x) {
    while(x<=N) {
        b[x]=a[x]; // 先用自己修改自己
        int lx=lowbit(x); // lx为[x-lowbit(x)+1, x]的区间长度
        for(int i=1; i<lx; i<<=1) {
            b[x]=max(b[x],b[x-i]);
        }
        x+=lowbit(x);
    }
}

区间查询

区间和的查询不必说，用两个前缀和相减即可：sum(y)-sum(x-1)。

但是最值并不满足线性性质，它的拓扑性质要求它不能仅仅是两个最值的相减。

我们想要的得到的是区间[x, y]上的最值，与[1, x-1]没有任何关系。

我们假设区间查询函数长这个样子：query(x, y)。
以最大值为例：
当y-lowbit(y)>=x时，[x, y]区间包含了[y-lowbit(y)+1, y]区间，因此可以直接使用b[y]的值:

$query(x,y)=max\left(b\right[y],query(x,y-lowbit\left(y\right)\left)\right);$query(x,y)=max(b[y],query(x,y−lowbit(y)));

当y-lowbit(y)<x时，上述包含关系不成立，因此只能先委屈的使用a[y]的值，然后将y减1:

$query(x,y)=max\left(a\right[y],query(x,y-1\left)\right);$query(x,y)=max(a[y],query(x,y−1));

然后再写成递推形式，那么简洁的代码又来了：

int query(int x, int y) {
    int ans=0;
    while(y>=x) {
        ans=max(ans,a[y]), --y;
        while(y-lowbit(y)>=x) {
            ans=max(ans,b[y]);
            y-=lowbit(y);
        }
    }
    return ans;
}

很明显，这还是一个O((logn)²)的算法，舒服。

最后，上一道模板题：HDU 1754 I Hate It

模板题就没啥好讲的啦 ^ O ^

I Hate It

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 117899 Accepted Submission(s): 43786

Problem Description
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input
本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取’Q’或’U’) ，和两个正整数A，B。
当C为’Q’的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。
当C为’U’的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。

Output
对于每一次询问操作，在一行里面输出最高成绩。

Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5

Sample Output
5
6
5
9

我的AC代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 2e5+5;

inline int read() {
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0', c=getchar();
    return x;
}

int N, M;
int a[maxn], b[maxn];

inline int lowbit(const int &x) { return x&-x; }

void updata(int x) {
    while(x<=N) {
        b[x]=a[x];
        int lx=lowbit(x);
        for(int i=1; i<lx; i<<=1) {
            b[x]=max(b[x],b[x-i]);
        }
        x+=lowbit(x);
    }
}

int query(int x, int y) {
    int ans=0;
    while(y>=x) {
        ans=max(ans,a[y]), --y;
        while(y-lowbit(y)>=x) {
            ans=max(ans,b[y]);
            y-=lowbit(y);
        }
    }
    return ans;
}

int main() {
    //ios::sync_with_stdio(false);
    while(scanf("%d%d", &N, &M)!=EOF) {
        memset(b,0,sizeof(b));
        for(int i=1; i<=N; ++i) a[i]=read(), updata(i);
        while(M--) {
            char c;
            int A, B;
            scanf("\n%c%d%d", &c, &A, &B);
            if(c=='Q') printf("%d\n", query(A,B));
            else if(c=='U') {
                a[A]=B;
                updata(A);
            }
        }
    }
}