【数据结构】树状数组

更新于 分类于 ， 阅读次数： 本文字数： 6.5k 阅读时长 ≈ 6 分钟

树状数组将线性结构转化成树状结构，在单点修改和前缀和（可以O(1)O(1) 求得区间和）方面表现优异（log级），相比线段树，应用范围窄，代码短，好写。

基本知识

  • 一个数字（非0）与它的相反数与，结果是二进制下这个数最靠右的1的位置，操作称作lowbit。
1
inline int lowbit(int x) { return x & -x; }
  • 树状数组的存放规则：第k位存放从k往前数lowbit(k)个数的和

  • 复杂度：空间O(N)O(N)，查询&修改时间复杂度O(log⁡N)O(\log N)

  • 基本都可以用线段树解决，没有线段树灵活

基本操作：单点修改，区间查询

目标

对于一个数组，支持在线单点修改操作与区间和查询操作

单点修改

下标不断+自己的lowbit，更新该下标的值，直到n为止

1
2
3
4
5
6
7
8
9
void update(int x, int k)
{
    if(x < 0) return;
    while (x <= n)
    {
        tree[x] += k;
        x += lowbit(x);
    }
}

区间查询

查询[1,x][1,x] 区间和，x作为下标不断减去自己的lowbit，直到0 ，每次将tree[x]加入答案中，利用前缀和可以求出任意区间[x,y][x,y] 的和query(y)-query(x-1)

1
2
3
4
5
6
7
8
9
10
int query(int x)
{
    int sum = 0;
    while (x > 0)
    {
        sum += tree[x];
        x -= lowbit(x);
    }
    return sum;
}

改进：实现区间修改与区间查询

  • 设差分数组did_i ，则每个点的值ai=∑i=1ndia_i=\sum_{i=1}^{n}d_i 。

  • 区间修改[l,r][l,r] ：每个元素+k+k ，即dl←dl+k,dr+1←dr+1−kd_l\leftarrow d_l+k,d_{r+1}\leftarrow d_{r+1}-k ，将差分数组建成树状数组，则区间修改对应修改单点值。

  • 单点查询：求[1,x][1,x] 区间和即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 第一种写法：用差分值直接建树，对于每次查询输出就可以
//原始值
for (int i = 1; i <= n; i++)
{
    cin >> val;
    update(i, val);
    update(i + 1, -val);
}
//修改[l,r]+k
update(l, k);
update(r+1, -k);
//查询x
cout << query(x) << endl;

// 第二种写法：储存原始值，每次查询输出原始值+差分数组值
//原始值
for (int i = 1; i <= n; i++)
    cin >> a[i];
//修改操作同第一种
//查询x
cout << a[x] + query(x) << endl;
  • 区间查询：∑i=1nai=∑i=1n∑j=1idj=∑i=1n(n−i+1)di=(n+1)∑i=1ndi−∑i=1nidi\sum_{i=1}^{n}a_i=\sum_{i=1}^{n}\sum_{j=1}^{i}d_j=\sum_{i=1}^{n}(n-i+1)d_i=(n+1)\sum_{i=1}^{n}d_i-\sum_{i=1}^{n}id_i ，维护两个树状数组，did_i 和idiid_i ，修改相应单点修改的参数就可以了。
1
2
3
4
5
6
7
8
9
10
// 将树状数组封装成结构体，T1是差分数组，T2是id_i，修改[l,r]+k
T1.update(l, k);
T1.update(r + 1, -k);
T2.update(l, l * k);
T2.update(r + 1, (r + 1) * (-k));
// [1,x]区间和查询
inline int query(int x)
{
    return (x + 1) * T1.query(x) - T2.query(x);
}

题目

洛谷P5459

洛谷P6186

洛谷P6186 [NOI Online #1 提高组] 冒泡排序

逆序对与冒泡排序性质的研究+权值树状数组，两种方法

题解首发于CSDN博客2022.1.8 NOI Online #1 提高组] 冒泡排序：【冒泡排序】与【逆序对】问题default111的博客-CSDN博客

题意

nn 元排列pip_i ，两种操作：

1 x：交换当前排列中xx 和x+1x+1 位置的数。

2 x：输出当前排列经过xx 轮冒泡排序交换后的逆序对个数。

输入输出

输入：单组数据，nn 排列长度，mm 操作数，nn 元排列，mm 个操作。

输出：每个一行，操作22 的结果。

数据范围

2≤n,m≤2e52\leq n,m\leq 2e5 ，操作22 中xx 在intint 范围，其他输入数保证合法。

分析

开始毫无头绪，我太笨了，看题解都看了好久，把两种方法整理一下TAT

从逆序对和冒泡排序的本质出发：

  • 逆序对，对于数组中的一个数xx 来说，向左找逆序对的个数为它左边比它大的数的个数。

  • 冒泡排序的一轮，本质是对于每个数，如果左边没有比它大的，会向右换到第一个比它大的数左边；反过来说，如果一个数左边有xx 个比它大的数，那么每轮让左边最近的大数交换到右边，逆序对个数−1-1 ，xx 轮后（即x+1x+1 轮），它开始向右交换。

记原排列为a[1...n]a[1...n]，b[i]b[i] 表示a[i]a[i] 左边比它大的数的个数，则逆序对的个数为∑i=1nb[i]\sum_{i=1}^{n} b[i] 。

考虑操作二，每一轮冒泡排序，若b[1...n]b[1...n] 不为00 则减11，则第xx 轮的逆序对个数为：

∑i=1nb[i]−∑i=1nmin(b[i],x)=∑b[i]>xb[i]−x∑b[i]>x1\sum_{i=1}^{n} b[i]-\sum_{i=1}^{n}min(b[i],x)=\sum_{b[i]>x} b[i]-x\sum_{b[i]>x} 1

  • 方法一：右边的式子是很明显的两颗权值线段树！

  • 方法二：观察第一个式子，第一项可以在读入数据时建立权值线段树求解得到；第二项f(x)=∑i=1nmin(b[i],x)=f(x−1)+b[i]≥x的个数f(x)=\sum_{i=1}^{n}min(b[i],x)=f(x-1)+b[i]\geq x的个数 得到。因为0≤b[i]<n0\leq b[i]<n ，开一个桶d[c]d[c] 记录b[1...n]==cb[1...n]==c 的个数，则f(x)=f(x−1)+∑i=xn−1d[i]=f(x−1)+n−∑i=0x−1d[i]f(x)=f(x-1)+\sum_{i=x}^{n-1}d[i]=f(x-1)+n-\sum_{i=0}^{x-1}d[i]，其中f(0)=0f(0)=0。有了f(x)−f(x−1)=n−∑i=0x−1d[i]f(x)-f(x-1)=n-\sum_{i=0}^{x-1}d[i]，建一棵线段树/树状数组，每次求区间和就可以得到f(x)f(x) 了！而如果我们把线段树/树状数组略作修改，将第一个节点设为∑i=1nb[i]\sum_{i=1}^{n} b[i]，并依次加入∑i=0x−1d[i]−n\sum_{i=0}^{x-1}d[i]-n 节点，就可以通过一个直接的[1...x][1...x] 区间求和得到答案！

至此，仅操作22 ，即对于一个序列求任意轮冒泡排序后逆序对个数的问题解决了。

操作11 会产生什么影响呢？只交换相邻两个，只能影响到它们俩有关的量。

  • 方法一：直接更新两棵权值线段树就好了！
  • 方法二：考虑交换a[i],a[i+1]a[i],a[i+1] （同步交换bb 数组），初始逆序对个数发生±1\pm 1 的改变；另外相当于把dd 的两个相邻的桶(d[b[i]]和d[b[i]−1]，或d[b[i+1]]和d[b[i+1]+1])(d[b[i]]和d[b[i]-1]，或d[b[i+1]]和d[b[i+1]+1]) ，做了修改（左+1右-1或反过来），那么只需要修改左边那个桶对应的上述树状数组的节点值即可！

至此，分析完了（吐血）。

代码

注意long long

方法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
int n,m;
int a[N],b[N]; // a是原始排列，b是左边比它大的数的个数
struct BIT
{
    ll tree[N];
    inline int lowbit(int x) { return x & (-x); }
    inline void init() { memset(tree,0,sizeof(tree)); }
    inline void update(int x,int val=1)
    {
        if(!x)
            return;
        //cout<<x<<' '<<val<<":\n";
        while(x<=n)
        {
            //cout<<x<<endl;
            tree[x]+=val;
            x+=lowbit(x);
        }
    }
    inline ll query(int x)
    {
        ll sum=0;
        while(x>0)
        {
            sum+=tree[x];
            x-=lowbit(x);
        }
        return sum;
    }
    inline ll query(int l,int r) { return query(r)-query(l-1); }
}origin,number;
int main()
{
    read(n),read(m);
    for(int i=1;i<=n;i++)
    {
        read(a[i]);
        b[i]=i-1-origin.query(a[i]-1); // 求左边比a[i]大的数的个数
        origin.update(a[i]); // 插入a[i]
    }
    origin.init();
    for(int i=1;i<=n;i++)
    {
        origin.update(b[i],b[i]); // \sum b[i]
        number.update(b[i]); // \sum 1
    }
    int op,x;
    for(int i=1;i<=m;i++)
    {
        read(op),read(x);
        if(op==2)
            printf("%lld\n",x>=n?0:origin.query(x+1,n)-x*number.query(x+1,n));
        else
        {
            if(a[x]>a[x+1])
            {
                origin.update(b[x+1],-b[x+1]);
                number.update(b[x+1],-1);
                b[x+1]--;
                origin.update(b[x+1],b[x+1]);
                number.update(b[x+1],1);
            }
            else
            {
                origin.update(b[x],-b[x]);
                number.update(b[x],-1);
                b[x]++;
                origin.update(b[x],b[x]);
                number.update(b[x],1);
            }
            swap(a[x],a[x+1]);
            swap(b[x],b[x+1]);
        }
    }
    return 0;
}

方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
int n,m;
int a[N],b[N],d[N]; // a是原始排列，b是左边比它大的数的个数，d是桶
ll tree[N];
inline void update(int x,ll val=1)
{
    if(!x)
        return;
    //cout<<x<<' '<<val<<":\n";
    while(x<=n)
    {
        //cout<<x<<endl;
        tree[x]+=val;
        x+=lowbit(x);
    }
}
inline ll query(int x)
{
    ll sum=0;
    while(x>0)
    {
        sum+=tree[x];
        x-=lowbit(x);
    }
    return sum;
}
int main()
{
    read(n),read(m);
    ll cnt=0; // 记录初始逆序对个数
    for(int i=1;i<=n;i++)
    {
        read(a[i]);
        b[i]=i-1-query(a[i]-1); // 求左边比a[i]大的数的个数
        update(a[i]); // 插入a[i]
        d[b[i]]++;
        cnt+=b[i];
    }
    memset(tree,0,sizeof(tree));
    update(1,cnt); // 第一个节点记录原逆序对数a
    cnt=0; // 用来求d数组的和
    for(int i=0;i<n;i++)
    {
        cnt+=d[i];
        update(i+2,cnt-n); // 注意第一个节点已经加过了，所以是i+2
    }
    int op,x;
    for(int i=1;i<=m;i++)
    {
        read(op),read(x);
        if(op==2)
            printf("%lld\n",x>=n?0:query(x+1));
        else
        {
            if(a[x]>a[x+1])
            {
                update(1,-1); // 总数-1
                b[x+1]--;
                update(b[x+1]+2); // 左+1右-1
            }
            else
            {
                update(1);
                update(b[x]+2,-1); // 左-1右+1
                b[x]++;
            }
            swap(a[x],a[x+1]);
            swap(b[x],b[x+1]);
        }
    }
    return 0;
}