Frosti

数据结构Part 1

Thu Dec 12 2024
8 minutes
算法学习笔记 OI 数据结构
1656 words

0.树状数组#

lowbit 运算#

定义一个二进制数 xx 最低位的 11 与后面的 00 组成的 100…0100 \ldots 0 为 lowbit(x)lowbit(x)。

其求法为 x&−xx \& -x

树状数组#

树状数组每个节点维护的是原数组的一段和（不一定是加法的和），先看一张图：

这张图就是树状数组一个节点维护的和。

那到底怎么维护的呢？实际上，cxc _ x 维护的是 [ax−lowbit(x)+1,ax][a _ {x - lowbit(x) + 1},a _ x] 的信息。

区间查询#

我们发现，[a1,ax][a _ 1,a _ x] 的前缀和可以在树状数组上在 O(log⁡x)\Omicron(\log x) 的复杂度内得出。因为我们可以把其拆成几段，然后用树状数组求出。

比如 7=111(2)7 = 111 _ {(2)}，所以我们可以将 ∑i=17ai\sum _ {i = 1} ^ 7 a _ i 拆成 c7+c6+c4c _ 7 + c _ 6 + c _ 4。此时，我们可以发现，下标每次都是减去了其的 lowbit 值，所以我们可以这么写：

CPP
1
2
3
4
5
6
7
8
inline int query(int pos)
{
    int res = 0;
    for(int i = pos;i;i -= lowbit(i))
        res += c[i];
    return res;
}
#define seqQuery(l,r) (query(r) - query(l - 1))

然后这个查出来就是 ∑i=1posai\sum _ {i = 1} ^ {pos} a _ i。

所以任意的 [l,r][l,r] 就可以通过查询 [1,r]−[1,l−1][1,r] - [1,l - 1] 得出。

单点修改#

前面说了，树状数组维护的是一段区间。所以单点修改需要对涉及的区间全部修改一下。

又因为每次都是按 lowbit 值来跳，所以很容易的就可以得出代码。

CPP
1
2
3
4
5
inline void modify(int pos,int x)
{
    for(int i = pos;i <= n;i++)
        c[i] += x;
}

区间修改#

这个需要结合差分的知识。

因为 ∑i=1nai=∑i=1n∑j=1idj=∑i=1ndi×(n+1)−∑i=1ndi×i\sum _ {i = 1} ^ {n} a _ i= \sum _ {i = 1} ^ n \sum _ {j = 1} ^ id _ j = \sum _ {i = 1} ^ n d _ i \times (n + 1) - \sum _ {i = 1} ^ n d _ i \times i

所以我们可以维护两个树状数组，分别维护 did _ i 与 di×id _ i \times i。

区间修改时，我们先对 c1l{c _ 1} _ l 加上 kk,c1r+1{c _ 1} _ {r + 1} 减去 kk，再对 c2l{c _ 2} _ l 加上 k×lk \times l，c2r+1{c _ 2} _ {r + 1} 减去 k×(r+1)k \times (r + 1)，这样就好了。

代码如下

CPP
1
2
3
4
5
6
7
8
9
10
11
12
inline void modify(int pos,int k)
{
    for(int i = pos;i <= n;i += lowbit(i)) //a[1...pos] += k
        c1[i] += k,c2[i] += pos * k;
}
inline int query(int pos) //a[1]...a[pos]
{
    int res = 0;
    for(int i = pos;i;i -= lowbit(i))
        res += (i + 1) * c[i] - c2[i];
    return res;
}

复杂度#

空间复杂度 Θ(n)\Theta (n)，时间复杂度 Θ(log⁡n)\Theta(\log n)，并且常数大大优于线段树，码量大大少于线段树。

实质#

就像线段树维护的是一个幺半群，树状数组同理，事实上，树状数组可维护的信息是线段树的子集。

所以，树状数组也可以维护 gcd⁡,max⁡,\gcd,\max, 乘法等信息。

二维树状数组#

别名树状数组套树状数组。

对于每行的树状数组，就是一个一维树状数组。

然后，外层的树状数组管辖区间是一致的。

二维差分#

di,j=ai,j−ai−1,j−ai,j−1+ai−1,j−1d _ {i,j} = a _ {i,j} - a _ {i - 1,j} - a_ {i,j - 1} + a _ {i - 1,j - 1}

对于一个子矩阵的修改，相当于 da,b,dc+1,d+1+=v,dc+1,d,da,b+1−=vd _ {a,b},d _ {c + 1,d + 1} += v,d _ {c + 1,d},d _ {a,b + 1} -= v（记忆方法：右下角一定加一，然后错排）

又因为有 ∑i=1n∑j=1mai,j=∑i∑j∑x=1i∑y=1jdx,y=∑i∑jdi,j×(xy+x+y+1−i(y+1)−j(x+1)+ij)\sum _ {i = 1} ^ n \sum _ {j = 1} ^ m a _ {i,j} = \sum _ i \sum _ j \sum ^ i _ {x = 1} \sum ^ j _ {y = 1} d _ {x,y} = \sum _ i \sum _ j d _ {i,j} \times (xy + x + y + 1 - i(y + 1) - j(x + 1) + ij)

所以可以考虑维护四个树状数组（我真 tm 不想写），来求子矩阵和。

CPP
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
#define lowbit(x) (x & -x)
inline void add(int x,int y,int val)
{
    for(int i = x;i <= n;i += lowbit(i))
    {
        for(int j = y;j <= m;j += lowbit(j))
        {
            c1[i][j] += val;
            c2[i][j] += val * x;
            c3[i][j] += val * y;
            c4[i][j] += val * x * y;
        }
    }
}
inline void modify(int a,int b,int c,int d,int val)
{
    add(a,b,val);
    add(a,d + 1,-val);
    add(c + 1,b,-val);
    add(c + 1,d + 1,val);
}
inline int pre_query(int x,int y)
{
    int res = 0;
    for(int i = x;i;i -= lowbit(i))
    {
        for(int j = y;j;j -= lowbit(j))
            res += (x + 1) * (y + 1) * c1[i][j] - (y + 1) * c2[i][j] - (x + 1) * c3[i][j] + c4[i][j];
    }
    return res;
}

inline int query(int a,int b,int c,int d)
{
    return pre_query(c,d) - pre_query(c,b - 1) - pre_query(a - 1,d) + pre_query(a - 1,b - 1);
}

权值树状数组#

这个东西可以解决全局 kk 小值，二维偏序问题

其实就是对权值数组建树状数组，然后就好了。

关于逆序对，可以枚举 i←[n,1]i \gets [n,1]，然后求权值的前缀和，kk 小值就是枚举 i←[log⁡2x,0]i \gets [\log _ 2 x,0]，然后每次查询前缀和，若 sum+[x+1,x+2i]<ksum + [x + 1,x + 2 ^ i] \lt k 则扩展，最后 x+1x + 1 即为答案。

然后树状数组就差不多了，剩下的线段树那讲。

Addition. Tricks#

动态开点#

其实就是一个存储的 Trick，在点分树里面，可能需要对每个节点都开树状数组，如果直接开是 O(n2)\Omicron(n ^ 2) 的空间复杂度。

这个时候，我们就可以把静态数组换成 vector，根据需要来开。

你甚至可以直接继承 vector<int> 来封装一个动态开点树状数组。

线性建树#

因为树状数组管辖的是 [x−lowbit(x)+1,x][x - lowbit(x) + 1,x] 的信息，所以我们可以预处理前缀数组 sumsum，然后用 sumsum 来计算树状数组每一个位置的值。

树状数组套树#

如果你学过主席树，那你应该知道，线段树是可以进行前缀和的。

能方便的维护前缀和的数据结构有什么？树状数组！

具体就是树状数组每个节点存的是你需要的一种树，修改就像普通树状数组一样，在对应点位修改。

查询可以先把所有的根节点存下来，然后在内层树操作的时候同时操作所有节点。

里面什么都能套，个人经验：里面套线段树空间开销会大一点，套平衡树时间开销会大一点。

维护后缀的树状数组#

可以直接把普通树状数组的修改和查询的枚举方式互换一下。