树状数组讲课

前言

首先来看一个问题：给定a数组单点修改，询问区间和。
显然我们有两种思路
1.不维护任何东西，直接用a数组 O(1)修改 O(n)求和
2.维护a的前缀和，O(n)修改 O(1)求和
可是这两种方法都太极端了，我们想均衡一下这两种算法。
观察可知前缀和O(n)修改是因为sum[i]维护的是[1,i]的和。区间太大了，所以我们能不能维护小一些的区间。这就是树状数组的思想。

定义

给出数组a，它的树状数组为t，t[i]为a[i-lowbit(i)+1]到a[i]的和。
图片说明
维护区间和

单点修改、区间询问(前缀和)

区间修改、单点询问(差分数组)

差分思想，BIT维护一个差分数组
设a数组为原数组，数组d为差分数组(d[i] = a[i]-a[i-1]),那么a[i] = d[1]+d[2]+…+d[i]。
所以求a[i]就可以用树状数组维护d[i]的前缀和
根据d的定义，在[l,r]区间上加上x(减去类似)，对于d数组来说只有a[l]和a[l-1]的差增加了x，a[r+1]和a[r]的差减少了x，所以需要修改这两个位置。
即add(l,x)，add(r+1,-x)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
int t[maxn];
int lowbit(int x){return x&-x;}
void add(int i,int val){
    for(;i<maxn;i+=lowbit(i))
        t[i]+=val;
}
ll sum(int i){
    ll ans = 0;
    for(;i>0;i-=lowbit(i))
        ans += t[i];
    return ans;    
}
const int maxn = 2e5+5;
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&);
    }
    for(int i=0;i<m;i++){
        scanf("%d%d%d%d",)
    }
    return 0;
}

树状数组的用途

区间和
区间最值
求逆序数
k-th大

求逆序数

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

离散化

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。

通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。
例如：
原数据：1,999,100000,15；处理后：1,3,4,2；

推荐例题：洛谷P1955

区间最值

只支持单点修改和区间查询最值。
和前面维护区间和的BIT类似，t[x]存储的区间[x,x-lowbit(x)+1)中的每个数的最大值，数组a为原数组。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
int t[maxn],a[maxn];
int n,m,x;
int lowbit(int x){return x&(-x);}
void update(int x){
    for(;x<=n;x+=lowbit(x)){
        t[x] = a[x];
        for(int i=1;i<lowbit(x);i<<=1){
            t[x] = max(t[x],t[x-i]);
        }
    } 
} 

int query(int l,int r){
    int ans = 0;
    while(r>=l){
        ans = max(ans,a[r]);
        r--;
        for(;r-lowbit(r) >= l;r-=lowbit(r))
            ans =  max(ans,t[r]);
    }
    return ans;
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        memset(t,0,sizeof(t));
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),update(i);
        char op[10];
        int y;
        for(int i=1;i<=m;i++){
            scanf("%s",op);
            scanf("%d%d",&x,&y);
            if(op[0] == 'U') a[x]=y,update(x);
            else printf("%d\n",query(x,y));
        }
    }
    return 0;
}

第k大
周末再讲