树状数组、线段树与RMQ

2021-03-17 约 2400 字预计阅读 5 分钟 - 次阅读

区间修改问题常用的三种手段，我觉得还是有必要复习一下。

树状数组

binary index tree 来自OI-wiki的图，我记得刘汝佳书里也有，不过那本书不在我手边 fenwick1

树状数组的核心是lowbit：x&(-x)，其中-x为x的负数的补码表示形式，计算出来可以得到x的二进制从右往左的第一个1所对应的十进制数字。这样就可以算出非叶子节点对应的管辖范围

单点修改，一路上山

int tree[MAXN];
inline void update(int i, int x)
{
    for (int pos = i; pos < MAXN; pos += lowbit(pos))
        tree[pos] += x;
}

求前n项和，一路下山

inline int query(int n)
{
    int ans = 0;
    for (int pos = n; pos; pos -= lowbit(pos))
        ans += tree[pos];
    return ans;
}

区间查询

inline int query(int a, int b)
{
    return query(b) - query(a - 1);
}

举个例子，查询前6个的和，lowbit(6) =2 ，所以S[6] = c[6]+c[4]，这是比较自然的。更新的时候，如果要更新6的话，需要更新c[6]和c[8]的值。唯一的问题就是需要多加理解，二进制表示毕竟不够直观。但是原题目是很简单的。

RMQ

Range Maximum query，区间查找算法。同样出现在刘汝佳的书里面。该算法的核心是二分法，就是将对一个区间的查找转变为对不断二分的子区间的查找，其中子区间长度均为2的倍数。

因为找不到书了，参考网上的代码

建立

假设有一个数组：1,2,6,8,4,3,7 设二维数组dp[i][j]表示从第i位开始连续2^j个数中的最小值。例如dp[2][1]表示第二位数开始连续两个数的最小值，也就是第二位数和第三位数的最小值，即2. 在求的时候可以将其分为两个部分，第一部分是$i$到$i+2^{j-1}-1$，第二部分是$i+2^{j-1}$到$i+2^{j}-1$。

显然初始值dp[i][0]为数本身，因此转移方程还是比较好求的 dp[i][j] = min(dp [i][j - 1], dp [i + (1 << j - 1)][j - 1])，也即第一部分和第二部分的最小值在求解。

代码

void rmq_init()
{
    for(int i=1;i<=N;i++)
        dp[i][0]=arr[i];//初始化
    for(int j=1;(1<<j)<=N;j++)
        for(int i=1;i+(1<<j)-1<=N;i++)
            dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
}

注意循环变量的顺序不可改变。这相当于就是不断增加区间的长度来更新所有的状态。另外第二部分是可以超过数组长度限制的，这不影响最终的结果。

查询

假设需要查询区间[l,r]的最小值，令$k=log2(r-l+1)$，区间最小值RMQ[l,r] = min(dp[l][k], dp[r - (1 « k) + 1][k]);，即从左边和右边同时开始搜索的最小值。证明过程就略了，毕竟也不是搞算法的。这里刘汝佳算法竞赛训练指南那幅图比较直观，查询时其实就是从两端伸出了两个块，只要保证2^k大于等于区间的一半，则最小值一定是能算出来的。

线段树

参考资料特点是能够在O(logN)的时间复杂度内实现单点修改、区间修改、区间查询（区间求和、求区间最大值、求区间最小值等）求区间最值用线段树，我的理解是在修改操作较多的时候这样会更好一些。毕竟RMQ每次修改后都要更新一遍dp数组，速度其实也不快。

核心思想也是二分法，把大区间分成两个小区间管理，直到区间长度为1为止。区间索引按照完全二叉树，所以位置为x的节点其孩子分别为2x与2x+1

树建立参考

递归方法建立线段树，其中d数组保存着树节点，a数组保存着原始数据

void build(int s, int t, int p) {
  // 对 [s,t] 区间建立线段树,当前根的编号为 p
  if (s == t) {
    d[p] = a[s];
    return;
  }
  int m = (s + t) / 2;
  build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
  // 递归对左右区间建树
  d[p] = d[p * 2] + d[(p * 2) + 1];
}

区间查询

以求和为例子，查询区间[3,5]的和，可以用【3,3】+【4,5】来得到最终结果。示例代码

int getsum(int l, int r, int s, int t, int p) {
  // [l,r] 为查询区间,[s,t] 为当前节点包含的区间,p 为当前节点的编号
  if (l <= s && t <= r)
    return d[p];  // 当前区间为询问区间的子集时直接返回当前区间的和
  int m = (s + t) / 2, sum = 0;
  if (l <= m) sum += getsum(l, r, s, m, p * 2);
  // 如果左儿子代表的区间 [l,m] 与询问区间有交集,则递归查询左儿子
  if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
  // 如果右儿子代表的区间 [m+1,r] 与询问区间有交集,则递归查询右儿子
  return sum;
}

区间维护

如果在修改的时候将所有区间内节点进行修改，代价将难以承受。线段树使用的是”懒惰标记“，即在父节点缓存下更改，这样在查询的时候可以直接累加上对应的修改值。

实例代码1

区间求和

void update(int l, int r, int c, int s, int t, int p) {
  // [l,r] 为修改区间,c 为被修改的元素的变化量,[s,t] 为当前节点包含的区间,p
  // 为当前节点的编号
  if (l <= s && t <= r) {
    d[p] += (t - s + 1) * c, b[p] += c;
    return;
  }  // 当前区间为修改区间的子集时直接修改当前节点的值,然后打标记,结束修改
  int m = (s + t) / 2;
  if (b[p] && s != t) {
    // 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
    d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
    b[p * 2] += b[p], b[p * 2 + 1] += b[p];  // 将标记下传给子节点
    b[p] = 0;                                // 清空当前节点的标记
  }
  if (l <= m) update(l, r, c, s, m, p * 2);
  if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
  d[p] = d[p * 2] + d[p * 2 + 1];
}
int getsum(int l, int r, int s, int t, int p) {
  // [l,r] 为查询区间,[s,t] 为当前节点包含的区间,p为当前节点的编号
  if (l <= s && t <= r) return d[p];
  // 当前区间为询问区间的子集时直接返回当前区间的和
  int m = (s + t) / 2;
  if (b[p]) {
    // 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
    d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m),
        b[p * 2] += b[p], b[p * 2 + 1] += b[p];  // 将标记下传给子节点
    b[p] = 0;                                    // 清空当前节点的标记
  }
  int sum = 0;
  if (l <= m) sum = getsum(l, r, s, m, p * 2);
  if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
  return sum;
}

区间直接修改为某个值而不是加上某个值

void update(int l, int r, int c, int s, int t, int p) {
  if (l <= s && t <= r) {
    d[p] = (t - s + 1) * c, b[p] = c;
    return;
  }
  int m = (s + t) / 2;
  if (b[p]) {
    d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m),
          b[p * 2] = b[p * 2 + 1] = b[p];
    b[p] = 0;
  }
  if (l <= m) update(l, r, c, s, m, p * 2);
  if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
  d[p] = d[p * 2] + d[p * 2 + 1];
}
int getsum(int l, int r, int s, int t, int p) {
  if (l <= s && t <= r) return d[p];
  int m = (s + t) / 2;
  if (b[p]) {
    d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m),
          b[p * 2] = b[p * 2 + 1] = b[p];
    b[p] = 0;
  }
  int sum = 0;
  if (l <= m) sum = getsum(l, r, s, m, p * 2);
  if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
  return sum;
}