day1 DS1

堆

堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。

每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆。STL 中的 priority_queue 默认是一个大根堆。

堆的操作

所有堆都（高效地）支持：插入一个数（push）、查询最小/最大值（top）、删除最小/最大值（pop）。

有一些堆（高效地）支持：合并两个堆（merge）、减小一个元素的值、……

堆的时间复杂度

不同的堆在执行不同的操作时时间复杂度各不相同，这里只介绍二叉堆（普通堆）和左偏树（可并堆）两种常用堆：

二叉堆

STL 中的 priority_queue 就是一个二叉堆。

结构

二叉堆是一棵二叉树，并且是完全二叉树，每个结点上存储一个元素。

堆的性质：父亲的权值不小于儿子的权值（大根堆）。

由堆的性质，树根存的是最大值（top 操作直接返回根上存储的元素即可）。

push 操作

push 操作向二叉堆中插入一个新元素，要保证操作后仍是一棵完全二叉树。

最简单的方法就是，最下一层最右边的叶子之后插入；如果最下一层已满，就新增一层。

这样操作后得到的二叉树并不一定满足堆的性质，需要再进行一些调整（把新插入的结点向上移动）：

• pushup(x)：如果结点 $x$ 的权值大于 ${pnt}_x$ 的权值，就交换 $x$ 与 $pn{t}_x$，重复此过程直到 ${val}_x\le {val}_{{pnt}_x}$ 或 $x$ 成为根。
• 时间复杂度 $\mathcal{O}(\log n)$。

pop 操作

pop 操作删除堆中最大的元素所在的结点，即根结点。

如果直接删除，产生了两个堆，难以处理（？）。

不妨考虑 push 操作的逆过程，如果能将根结点移到最后一个结点，那么就可以直接删掉它。然而直接移动难以实现，所以我们先把根结点和最后一个结点交换，删掉原来的根节点。

这样操作后得到的二叉树并不一定满足堆的性质，也需要再进行一些调整（把新的根结点向下移动）：

• pushdown(x)：在 $x$ 的两个儿子中，找一个元素最大的，与该结点交换，重复此过程直到 $x$ 成为叶结点。
• 时间复杂度 $\mathcal{O}(\log n)$。

实现

考虑使用一个序列 $h$ 来表示堆。 $h_i$ 的两个儿子分别是 $h_{2i}$ 和 $h_{2i+1}$ ， $1$ 是根结点：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YuQAXWW7-1598313811707)(…/images/binary-heap1.png)]

int h[N];
#define pnt (x>>1)
#define ls (x<<1)
#define rs (x<<1|1)
void pushup(int x) {
   
    while (x > 1 && h[x] > h[pnt]) std::swap(h[x], h[pnt]), x = pnt;
}
void pushdown(int x) {
   
    while (ls <= n) {
   
        int t = ls;
        if (rs <= n && h[rs] > h[ls]) t = rs;
        if (h[t] <= h[x]) return;
        std::swap(h[x], h[t]);
        x = t;
    }
}
int top() {
    return n ? h[1] : -1; }
void pop() {
    std::swap(h[1], h[n--]), pushdown(1); }
void push(int x) {
    h[++n] = x, pushup(n); }

例题

• 模板：堆

左偏树（可并堆）

左偏树是一种可并堆，具有堆的性质，可以快速合并。

$\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}$ 的定义和性质

对于一棵二叉树，我们定义 外节点 为左儿子或右儿子为空的节点，定义一个外节点的 $\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}$ 为 $1$ ，一个不是外节点的节点 $\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}$ 为其到子树中最近的外节点的距离加一。空节点的 $\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}$ 为 $0$ 。

一棵有 $n$ 个节点的二叉树，根的 $\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}$ 不超过 $\lceil \log (n+1)\rceil$（$\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}$ 性质），因为一棵根的 $\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}$ 为 $x$ 的二叉树至少有 $x-1$ 层是满二叉树，那么就至少有 $2^x-1$ 个节点。注意这个性质是所有二叉树都具有的，并不是左偏树所特有的。

左偏树的定义和性质

左偏树是一棵二叉树，它不仅具有堆的性质，并且是「左偏」的：每个节点左儿子的 $\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}$ 都大于等于右儿子的 $\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}$ 。

因此，左偏树每个节点的 $\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}$ 都等于其右儿子的 $\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}$ 加 $1$（左偏性质）。

需要注意的是， $\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}$ 不是深度， 左偏树的深度没有保证 ，一条向左的链也是左偏树。

核心操作 - 合并（merge)

合并两个堆时，由于要满足堆性质，先取值较大的那个根作为合并后堆的根节点，然后将这个根的左儿子作为合并后堆的左儿子，递归地合并其右儿子与另一个堆，作为合并后的堆的右儿子。为了满足左偏性质，合并后若左儿子的 $\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}$ 小于右儿子的 $\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}$ ，就交换两个儿子。

struct node{
   
    int val,ls,rs,d;
} h[N];
int merge(int x, int y) {
   
    if (!x || !y) return x | y;         // 若一个堆为空则返回另一个堆
    if (t[x].val < t[y].val) std::swap(x, y);  // 取值较大的作为根
    t[x].rs = merge(t[x].rs, y);        // 递归合并右儿子与另一个堆
    if (t[t[x].rs].d > t[t[x].ls].d)
        std::swap(t[x].ls, t[x].rs);    // 若不满足左偏性质则交换左右儿子
    t[x].d = t[t[x].rs].d + 1;          // 更新dist
    return x;
}

由于左偏性质，每递归一层，其中一个堆根节点的 $\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}$ 就会减小 $1$ ，又根据 $\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}$ 性质，合并两个大小分别为 $n$ 和 $m$ 的堆复杂度是 $O(\log n+\log m)$。

其它操作

• push：将单个节点视为一个堆，合并即可。

• pop：合并根的左右儿子即可。

• <mark>打标记：与线段树类似，左偏树上也可以通过标记实现任何可以被标记且不改变元素相对大小的操作，如：整堆加/减一个值、乘一个正数。在根打上标记，在执行 pop / merge 等操作时下传标记即可。</mark>

注意事项

一般需要用数组记录每个堆的堆顶编号/指针。

题目中通常需要操作的是「$x$ 所在的堆」，这时一般需要同时维护并查集用于查询「$x$ 所在的堆」的根结点。

例题

• 模板：左偏树/可并堆
• P1552 [APIO2012]派遣
• 「JLOI2015」城池攻占

树状数组

树状数组是基于分治的一种高效算法。

其最基本操作是单点修改、求前缀和，其他操作大都基于这两种操作实现。

优点：

1. 单次操作时间复杂度为 $\mathcal{O}(\log n)$ 且常数很小，实际运行效率远优于线段树

2. 空间复杂度 $\Theta (n)$，在某些场景下较线段树有极大优势

3. 理解以后很好写~~（不理解也很好背）~~

缺点：

适用范围比线段树小的多。树状数组能有的操作，线段树一定有；线段树有的操作，树状数组不一定有。

结构

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4ByUh5ZP-1598313811710)(…/images/fenwick1.png)]

树状数组的思想和线段树类似：用一个大节点表示一些小节点的信息，进行查询的时候只需要查询一些大节点而不是更多的小节点。

最下面的八个方块就代表存入 $a$ 中的八个数；他们上面的呈树状结构的方块就是维护着数组 $a$ 的树状数组 $c$。

很显然看出： $c_2$ 管理的是 $a_1\sim a_2$； $c_4$ 管理的是 $a_1\sim a_4$； $c_6$ 管理的是 $a_5\sim a_6$； $c_8$ 管理的是 $a_1\sim a_8$。

$lowbit$

$lowbit(x)$ 表示 $x$ 的二进制表示中最低位的 $1$ 对应的值。

例如： $x=88_{(10)}=01011000_{(2)}$，$lowbit(x)=1000_{(2)}$

有符号正整数的相反数的二进制表示为：原数按位取反再加一，$x$ 与 $-x$ 有且只有 $x$ 的二进制表示中最低位均为 $1$，将两者按位与后即得到 $lowbit(x)$。

即：$lowbit(x)=x\&-x$。

例如 :
$x=88_{(10)}=01011000_{(2)}$ ；
$-x=-88_{(10)}=\left(10100111_{(2)}+1_{(2)}\right)=10101000_{(2)}$ ；
$lowbit(x)=x\&(-x)=1000_{(2)}$ 。

查询操作

观察发现：$c_j$ 管理的区间长度为 $lowbit(j)$，即：$c_j$ 管理的区间为 $a_{j-lowbit(j)+1}\sim a_j$。

在查询 $a$ 的一个左端点为 $1$ 的区间时，只需要合并若干个 $c_j$ 上的信息。

任意正整数 $x$ 可以用二进制表示，比如：$13_{(10)}=1101_{(2)}$；

区间 $[1,x]$ 可以按照 $x$ 的二进制表示中为 $1$ 的位置被拆成至多 ${\log }_{2}x$ 个 $c_j$，保证了单次查询的复杂度为 $\mathcal{O}(\log n)$。

比如 $[1,13]$ 可以拆成：

1. $\left[1,2^3\right]=\left(0,2^3\right]$ 即 $\left(0_{(2)},1000_{(2)}\right]$，$lowbit\left(1000_{(2)}\right)=1000_{(2)}$
2. $\left[2^3+1,2^3+2^2\right]=\left(2^3,2^3+2^2\right]$ 即 $\left(1000_{(2)},1100_{(2)}\right]$，$lowbit\left(1100_{(2)}\right)=100_{(2)}$
3. $\left[2^3+2^2+1,2^3+2^2+2^0\right]=\left(2^3+2^2,2^3+2^2+2^0\right]$ 即 $\left(1100_{(2)},1101_{(2)}\right]$，$lowbit\left(1101_{(2)}\right)=1_{(2)}$

我们发现：区间[L,R]的长度为R的二进制表示中最低的非零位，记为lowbit®。

因此我们有：R-L+1=lowbit®，即：L=R-lowbit®+1。

更新操作

在更新 $a_i$ 时，要同时更新所有管理 $a_i$ 的 $c_j$，从 $c$ 中的结点 $i$ 开始更新，不断跳到父节点（$c$ 中 $i$ 的父节点为 $i+lowbit(i)$）继续更新，直到父节点出界为止。

每跳一次，区间长度扩大到原来的二倍，因此单次更新中最多跳 $\log n$ 次，时间复杂度 $\mathcal{O}(\log n)$。

void upd(int p, int v) {
   
    for(;p<=n;p+=p&-p)d[p]+=v;
}
int qry(int p){
   
    int r=0;
    for(;p;p-=p&-p)r+=d[p];
    return r;
}

注意事项

树状数组不支持 $0$ 做下标，若数据中出现 $0$ 需要整体 $+1$ 后再处理。

区间修改，区间求和

若维护序列 $a$ 的差分数组 $b$ ，此时我们对 $a$ 的一个前缀 $r$ 求和，即 ${\sum }_{i=1}^r{a}_i$ ，由差分数组定义得 $a_i={\sum }_{j=1}^i{b}_j$

进行推导

$$\begin{array}{rl}& \sum _{i=1}^r{a}_i\\ =& \sum _{i=1}^r\sum _{j=1}^i{b}_j\\ =& \sum _{i=1}^r{b}_i\times (r-i+1)\\ =& (r+1)\times \sum _{i=1}^r{b}_i-\sum _{i=1}^r{b}_i\times i\end{array}$$

区间和可以用两个前缀和相减得到，因此只需要用两个树状数组分别维护 $\sum b_i$ 和 $\sum i\times b_i$ ，就能实现区间求和。

二维树状数组

树状数组套树状数组：

• 最简单的一种树套树
• 直接套娃即可
• 在外层树状数组的每个节点上维护一棵树状数组
• 查询/更新时使用二重循环即可

树状数组上二分

类似于线段树上二分，树状数组上也可以进行二分。

使用树状数组上二分（可能需要预先离散化），可以 $\mathcal{O}(\log n)$ 查询第 $k$ 小/大元素，实现类似平衡树的效果。

主要思想是：按二进制位从高到低逐渐二分出答案。

int kth(int k) {
   
    int r = 0, t;
    for (int i = LOG_N; i>=0; --i) {
   
        t = r | 1 << i;     
        if (t <= n && d[t] < k)k -= d[t], r = t;
    }
    return r + 1;
}

树状数组的应用

• 统计逆序对
• 二维偏序
• 维护前缀 $max$ ->优化DP，如： LIS 问题
• ……

例题

• 树状数组 1：单点修改，区间查询
• 树状数组 3：区间修改，区间查询
• 二维树状数组 1：单点修改，区间查询
• 不普通平衡树
• 数星星
• 简单题