学习笔记——树状数组应用扩展

· · 个人记录

知识回顾

树状数组，是在每个位置i存储长度为lowbit(i)的区间之和，从而实现logN时间复杂度内单点修改、单点前缀和查询。附上代码（感谢@sjkmost神犇帮忙码的代码）：

#define lowbit(x) (x) & -(x)
template < typename T, int N >
struct BIT {
    T c[N];
    int n;
    void modify(int i, const T &rhs) { //单点修改
        for (; i <= n; i += lowbit(i))
            c[i] = c[i] + rhs;
    }
    T query(int i) { //单点前缀和查询
        T k = T();
        for (; i; i -= lowbit(i))
            k = k + c[i];
        return k;
    }
};

模板：洛谷P3374

扩展#1：区间修改，单点查询

树状数组的基本功能是单点修改、单点前缀和查询，如何利用此性质呢？其实并不复杂，可以存储差分数组dif，这样单点的前缀和便是该点的值，修改区间[l..r]的话就转化成修改l和r+1两点了。附上代码：

    if( opt == 1){ //区间修改
        a = read() , b = read() , c = read();
        dif.modify(a , c) ;
        dif.modify( b + 1 , -c) ;
    }
    else{ //单点查询
        pint( dif.query( read() ) );
        pchar('\n'); 
    }

模板：洛谷P3368

扩展#2: 区间修改，区间查询

乍一看这不可能用树状数组实现，我也想了好长时间，最后还是@sjkmost神犇给我指点迷津才想到。

首先我们想一想：若用树状数组存储差分，点i的前缀和有什么性质？

a_1$ = $dif_1 a_2$ = $dif_1$ + $dif_2 a_3$ = $dif_1$ + $dif_2$ + $dif_3

......

a_i$ = $dif_1$ + $dif_2$ + $dif_3$ + ... + $dif_i

仔细观察，就会发现点1被加了i次、点2被加了i-1次、点3被加了i-2次......点i被加了1次，呈一个金字塔状。这样看似可以维护了。

不过还是不能直接维护，我们再来观察一下，不难发现：若点i再加上i-1次、点i-1再加上i-2次、点i-2再加上i-3次...

a_1$ = $dif_1$ + $dif_2$ + $dif_3$ + ... + $dif_i a_2$ = $dif_1$ + $dif_2$ + $dif_3$ + ... + $dif_i a_3$ = $dif_1$ + $dif_2$ + $dif_3$ + ... + $dif_i

......

a_i$ = $dif_1$ + $dif_2$ + $dif_3$ + ... + $dif_i

就恰好成为i{a_i}了。i{a_i}很好求，现在问题就转化成维护

附上代码： ```cpp if( opt == 1 ) { //区间修改 k = read() ; dif1.modify( x , k ) ; dif1.modify( y + 1 , -k ) ; dif2.modify( x , k * x ) ; dif2.modify( y + 1 , ( -k ) * ( y + 1 ) ) ; } else { //区间查询 pint( ( dif1.query( y ) * ( y + 1 ) - dif2.query( y ) ) - ( dif1.query( x - 1 ) * x - dif2.query( x - 1 ) ) ) ; pchar('\n') ; } ``` 模板： 洛谷P3372（线段树模板1） ##### 总结 树状数组是一个很实用的数据结构，具有常数小、码量小、不易写挂等优点。虽然其功能看似局限性较大，但只要肯思考、肯创新，就会发现很多很多的扩展应用。学OI，就得勤思考，勤创新。