历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

树状数组复习笔记

作者：

真我Elysia , 2022-07-15 20:02:55 , 所有人可见 , 阅读 181

树状数组

原理：

树状数组的代码量较短，思维清晰，在解决单点修改时可采用树状数组。
基本的实现操作：

快速求前缀和
修改每一个数

树状数组工作原理

用一个大的节点来表示小节点的信息，如图上所示。

基本代码

// 基于二进制的操作，从右往左数第一个1。
int lowbit(int x){
    return x & -x;
}

修改区间和，将序列中第x个数加上k。
运用了前缀和的思想：[x,n]的前缀和累加上K。

// lowbit(x)的值作为每个区间的分界。
void add(int x, int k){
    for(int i = x; i <= n; i += lowbit(i)) t[i] += k;
}

查询序列前x个数的和

int ask(int x){
    int sum = 0;
    for(int i = x; i; i -= lowbit(i)) sum += t[i];
    return sum;
}

基本应用

求解逆序数

241. 楼兰图腾
在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了 n 个点，经测量发现这 n 个点的水平位置和竖直位置是两两不同的。

西部 314 认为这幅壁画所包含的信息与这 n 个点的相对位置有关，因此不妨设坐标分别为 (1,y1),(2,y2),…,(n,yn)，其中 y1∼yn 是 1 到 n 的一个排列。

西部 314 打算研究这幅壁画中包含着多少个图腾。

如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤i[HTML_REMOVED]yj,yj<yk，则称这三个点构成 V 图腾;

如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤i[HTML_REMOVED]yk，则称这三个点构成 ∧ 图腾;

西部314想知道，这 n个点中两个部落图腾的数目。

因此，你需要编写一个程序来求出 V 的个数和 ∧ 的个数。

输入格式
第一行一个数 n。

第二行是 n
个数，分别代表 y1，y2,…,yn

。
输出格式

两个数，中间用空格隔开，依次为 V 的个数和 ∧ 的个数。
数据范围
对于所有数据，n≤200000，且输出答案不会超过 int64。y1∼yn 是 1 到 n的一个排列。

输入样例：
5
1 5 3 2 4
输出样例：
3 4

思路：利用树状数组求解逆序数。
将每个节点看作一个∧的最高点或V的最低点，从右往左遍历数组记录树状数组中有没有比当前点大的数字或小的数字。

int n,m;
int a[N];
int tr[N];
LL low[N],great[N];
// tr 表示当前数字是否存在
// low存放当前节点左侧比它小的点
// great存放当前节点左侧比它大的点

int lowbits( int x )
{
    return x&-x;
}

LL ask( int x )
{
    LL ans = 0;
    for( int i = x ; i ; i -= lowbits(i) ) ans += tr[i];
    return ans;
}

void add( int x , int k )
{
    for( int i = x ; i <= n ; i += lowbits(i) ) tr[i] += k;
}

int main(){
    cin >> n;
    for( int i = 1 ; i <= n ; i++ )
        cin >> a[i];
    for( int i = 1 ; i <= n ; i++ )
    {
        int x = a[i];
        //从[x+1,n]中找比x大的数字有多少个
        great[i] += abs( ask(n)-ask(x) );
        //从[1,x-1]中找比x小的数字有多少个
        low[i] += ask( x-1 );
        //将x放入树状数组中，1表示当前数字存在
        add( x , 1 );
    }
    LL resV = 0 , resA = 0;
    memset( tr, 0 , sizeof tr );
    //清空树状数组，重新从右往左进行扫描
    //与上方操作类似
    for( int i = n ; i >= 1 ; i-- )
    {
        int x = a[i];
        //相乘就是图腾的数量
        resV += great[i]*abs( ask(n) - ask(x));
        resA += low[i]*ask(x-1);
        add( x , 1 );
    }

    cout << resV << ' ' << resA << endl;    
    return 0;
}

拓展应用

区间修改，单点查询

242. 一个简单的整数问题
给定长度为 N 的数列 A，然后输入 M行操作指令。
第一类指令形如 C l r d，表示把数列中第 l∼r个数都加 d。
第二类指令形如 Q x，表示询问数列中第 x个数的值。

对于每个询问，输出一个整数表示答案。
输入格式
第一行包含两个整数 N和 M。

第二行包含 N个整数 A[i]。

接下来 M 行表示 M 条指令，每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
数据范围
1≤N,M≤105,
|d|≤10000,
|A[i]|≤109

输入样例：
10 5
1 2 3 4 5 6 7 8 9 10
Q 4
Q 1
Q 2
C 1 6 3
Q 2

输出样例：
4
1
2
5

思路：来自算法进阶指南
tr[]数组存储的是维护指令的累计结果
每次在l处产生，在r+1处消除。
tr[1~x]代表的是a[]数组的变化情况。
算法进阶指南作者的思路真是太神奇了。orz
具体的讲解在代码中。

int n,m;
int a[N],tr[N];

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

LL ask( int x )
{   
    // 这边普通模板的ans = 0，因为我们普通模板求的是前缀和，所以这边有所不同。
    // tr[]数组中记录的当前区间累计的变化情况，所以我们需要对当前位置的a[x]进行修改。
    LL ans = a[x];
    for( int i = x ; i ; i -= lowbit(i) ) ans += tr[i]; 
    return ans;
}

void add( int x , int k ) 
{
    for( int i = x ; i <= n ; i += lowbit(i) ) tr[i] += k;
}


int main(){
    cin >> n >> m;
    for( int i = 1 ; i <= n ; i++ )
        cin >> a[i];
    while( m-- )  
    {
        string s;
        int t;
        cin >> s >> t;
        if( s == "Q" ){
            //
            cout << ask(t) << endl;
        }else {
            int l,r,d;
            cin >> r >> d;
            l = t;
            // 我们在tr[l]处+=d,tr[r+1]处-=d。
            // 这里运用到差分的知识。
            // [1,l) 前缀和不变 ， [l,r]前缀和增加了d 
            // [r+1,n]处为保持不变所以要减d
            add( l , d );
            add( r+1 , -d ); 
        }
    }
    return 0;
}