广东网站设计公司,那曲地区建设局网站,网站建设备案需要什么,友妙招链接【算法进阶详解 第一节】树状数组 前言树状数组基础树状数组原理树状数组能够解决的问题 树状数组提高树状数组区间加#xff0c;区间和操作二维树状数组 树状数组应用树状数组区间数颜色树状数组二维偏序 前言
树状数组在算法竞赛中十分常见#xff0c;其能解决二维数点区间和操作二维树状数组 树状数组应用树状数组区间数颜色树状数组二维偏序 前言
树状数组在算法竞赛中十分常见其能解决二维数点区间数颜色等问题还具有较小的常数是一个十分优秀的数据结构。如果文章有问题欢迎在评论区指出。
树状数组基础
树状数组原理
我们用前缀和问题引入树状数组。 给定一个长为 n n n 数组之后有 q q q 次操作操作分修改和查询两种修改数组中一个位置查询前缀和。 如果维护整个数组每一次修改是 O ( 1 ) O(1) O(1) 的但是查询要便利整个前缀复杂度 O ( n ) O(n) O(n) 1 s 1s 1s 难以通过如果维护前缀和每一次查询是 O ( 1 ) O(1) O(1) 的但是修改会影响到包含它的前缀的值复杂度 O ( n ) O(n) O(n) 1 s 1s 1s 内仍旧难以通过而树状数组可以在 O ( log ( n ) ) O(\log(n)) O(log(n)) 的时间内解决修改和查询两种做法复杂度十分优秀相当于平均了修改和查询的复杂度。
维护数组维护前缀和维护树状数组修改 O ( 1 ) O(1) O(1) O ( n ) O(n) O(n) O ( log ( n ) ) O(\log(n)) O(log(n))查询 O ( n ) O(n) O(n) O ( 1 ) O(1) O(1) O ( log ( n ) ) O(\log(n)) O(log(n))
树状数组中每一个元素 c i c_i ci 存储的是 i − l o w b i t ( i ) 1 i - lowbit(i) 1 i−lowbit(i)1 ~ i i i 的权值和其中 l o w b i t ( x ) lowbit(x) lowbit(x) 表示 x x x 从低位开始的第一个 1 1 1 的权值即 2 最低位算 0 位时的位数 2^{最低位算 0 位时的位数} 2最低位算0位时的位数形象表示如下图来自网上一张图片 其中树状数组中每个元素的值就是其所属区间覆盖的原数组的元素和。
对于修改第 i i i 位操作修改任意一个位置上的值变化的是包含其的所有区间通过找规律可以发现就是 i i i 从查询位置编号开始每次加上 l o w b i t ( i ) lowbit(i) lowbit(i)。 对于查询前 i i i 位操作查询那些区间能覆盖查询操作通过找规律可以发现就是 i i i 从查询位置编号开始每次减去 l o w b i t ( i ) lowbit(i) lowbit(i)。
树状数组的核心代码如下
int lowbit(int x)
{return x -x;
}void add(int x, int c)
{for (int i x; i n; i lowbit(i)) tr[i] c; // n 为数组长度tr为树状数组。
}int sum(int x)
{int res 0;for (int i x; i; i - lowbit(i)) res tr[i];return res;
}树状数组能够解决的问题
树状数组可以解决区间和问题查询两个前缀和相减即可树状数组还可以进行单点与原来取 m i n min min查询前缀最小值但是由于两个前缀最小值不能得到区间最小值所以树状数组这样做不能得到区间最小值。
树状数组提高
树状数组区间加区间和操作
题目链接
要求实现两种操作
将一个区间中所有数加上一个数。查询一个区间中所有数的和。
这个题直接把区间修改暴力拆成单点修改显然会超时。我们可以将原序列 a a a 变成差分序列 b b b这样区间 [ l , r ] [l, r] [l,r] 加上 x x x 就变成了将差分序列的第 l l l 项加上 x x x将第 r 1 r 1 r1 项减去 x x x单点查询就变成了前缀查询。若此时把区间查询暴力拆成单点查询仍旧难以通过。 我们把前缀和式子进行变换 ∑ i 1 x a i \sum_{i 1}^{x} a_i i1∑xai ∑ i 1 x ∑ j 1 i b j \sum_{i 1}^{x} \sum_{j 1}^{i} b_j i1∑xj1∑ibj ∑ i 1 x ( x − i 1 ) b i \sum_{i 1}^{x} (x - i 1)b_i i1∑x(x−i1)bi ( x 1 ) ∑ i 1 x b i − ∑ i 1 x i b i (x 1)\sum_{i 1}^{x} b_i - \sum_{i 1}^{x} ib_i (x1)i1∑xbi−i1∑xibi 于是我们维护两个树状数组分别储存 b i b_i bi 和 i b i ib_i ibi 的前缀和即可查询原序列的前缀和。两个前缀和相减就是题目中要求查询的区间和了。
二维树状数组
二维树状数组就是把一维树状数组扩展到二维中能够进行单点修改和二维前缀和查询具体做法就是把每个一维树状数组的元素再存一个新的一维树状数组。修改时枚举需要修改的树状数组每个树状数组单独修改查询时枚举需要查询的树状数组每个树状数组单独查询即可。设查询和修改的二维平面大小为 n × m n \times m n×m则二维树状数组时间复杂度为 O ( l o g ( n ) l o g ( m ) ) O(log(n)log(m) ) O(log(n)log(m))。
二维树状数组的核心代码如下
int lowbit(int x)
{return x -x;
}void add(int x, int y, int c)
{for (int i x; i n; i lowbit(i))for (int j y; j m; j lowbit(j))tr[i][j] c;
}int sum(int x, int y)
{int res 0;for (int i x; i; i - lowbit(i))for (int j y; j; j - lowbit(j))res tr[i][j];return res;
}树状数组应用
树状数组区间数颜色
原题链接
给定一个长度为 n n n 的数组每次查询一个区间 [ l , r ] [l, r] [l,r] 中不同值的个数。
直接在线做比较困难考虑离线按右端点排序从前往后按右端点扫描线。在树状数组中我们在最后一次出现的颜色对应的下标存 1 1 1否则存 0 0 0扫描线时加入一个颜色时如果之前没有出现过这个颜色就直接把当前位置加 1 1 1否则把前面最后一次出现当前颜色的下标减 1 1 1再把当前下标加上 1 1 1查询时直接查询区间和即可。
树状数组二维偏序
树状数组可以解决二维偏序问题。
所谓的二维偏序就是给定两个 1 1 1 ~ n n n 的数组 a a a 和 b b b对于每个 1 ≤ i ≤ n 1 \le i \le n 1≤i≤n计算满足如下条件的 j ( 1 ≤ j ≤ n ) j(1 \le j \le n) j(1≤j≤n) a i ≤ a j a_i \le a_j ai≤aj b i ≤ b j b_i \le b_j bi≤bj
具体解决方法可以先把所有下标以 a i a_i ai 为第一关建字 b i b_i bi 为第二关键字排序然后从前往后扫描每个下标当扫描到 a i a_i ai 时可能的 j j j 只能出现在 i i i 之前满足第一个限制且 i i i 后面不会在有 j j j后面只有两种情况 a i a j a_i a_j aiaj 和 a i a j a_i a_j aiaj第一种肯定不满足第二种因为第二关键字是 b i b_i bi所以后面只可能 b i ≥ b j b_i \ge b_j bi≥bj b i b j b_i b_j bibj 肯定不行 b i b j b_i b_j bibj 特判即可。
然后由于 i i i 之前 a i a_i ai 的限制一定满足所以只需处理 i i i 之前的下标 b i b_i bi 的限制即可。我们发现就是求 ∑ k 1 b i − 1 i 之前 k 的数的个数 \sum_{k 1}^{b_i - 1} i 之前 k 的数的个数 ∑k1bi−1i之前k的数的个数。我们把这个式子理解成前缀和维护一个数组每扫过一个数就把 b i b_i bi 为下标的位置 1 1 1查询前缀和可以用树状数组处理。时间复杂度 O ( n log ( n ) n log ( max b i ) ) O(n\log(n) n\log(\max b_i)) O(nlog(n)nlog(maxbi))如果 max b i \max b_i maxbi 太大可以先把 b i b_i bi 离散化再求解复杂度 O ( n log ( n ) ) O(n\log(n)) O(nlog(n))。
