区间修改线段树

beyoursven · 2024-10-01 12:00:33 · 个人记录

区间修改线段树

从代码开始学习区间修改

如果用暴力地单点修改叶子的方式处理区间修改，时间复杂度显然很大。

回忆区间查询：待查询的区间的答案是由若干个被查询区间所包含的极大区间合并而成的。

尝试应用到修改上，如果我们递归碰到了被修改查询区间完全覆盖的极大区间：

我们只对当前结点进行修改，并且退出递归
后续对该区间进行递归时，再将所需进行的修改下放给最优儿子区间，相当于从上到下扩散影响
需要记录在每个区间处记录对后续子树的影响，不包含当前结点；当前结点应直接被更新。

影响被称为懒标记，原来需要维护的信息简称为信息。可以证明，区间修改的时间复杂度和区间查询的时间复杂度相同，O(\log N)（信息修改、合并部分的时间复杂度为 O(1) 的情况下）。

区间修改，单点查询

以区间加修改，查询单点值为例。

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 1;

int n, m;

struct Node {  // 结点信息
  int len, sum;
};

struct Tag {  // 懒标记
  int add;
  bool operator==(const Tag &i) const {  // 判断懒标记相等
    return add == i.add;
  }
};

struct SegTree {
  Tag tag[MAXN << 2];
  Tag I = {0};  // 恒等映射

  Tag F(const Tag &tag1, const Tag &tag2) {  // 懒标记函数复合运算
    return {tag1.add + tag2.add};
  }

  void build(int o, int l, int r) {
    tag[o] = I;
    if (l == r) {
      return;
    }
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
  }

  void down(int o) {  // 懒标记下放
    if (tag[o] == I) {
      return;
    }
    tag[o << 1] = F(tag[o], tag[o << 1]);
    tag[o << 1 | 1] = F(tag[o], tag[o << 1 | 1]);
    tag[o] = I;
  }

  void modify(int o, int l, int r, int ql, int qr, Tag t) {  // 区间修改
    if (ql <= l && r <= qr) {
      tag[o] = F(t, tag[o]);
      return;
    }
    int mid = (l + r) >> 1;
    down(o);  // 处理以前的懒标记的下放
    if (ql <= mid) {
      modify(o << 1, l, mid, ql, qr, t);
    }
    if (qr > mid) {
      modify(o << 1 | 1, mid + 1, r, ql, qr, t);
    }
  }

  Tag query(int o, int l, int r, int i) {  // 单点查询
    if (l == r) {
      return tag[o];
    }
    int mid = (l + r) >> 1;
    down(o);
    return i <= mid ? query(o << 1, l, mid, i) : query(o << 1 | 1, mid + 1, r, i);
  }
} T;

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  T.build(1, 1, n);  // 必须要写，需要初始化 len
  for (int i = 1, op, l, r, v, x; i <= m; i++) {
    cin >> op;
    if (op == 1) {
      cin >> l >> r >> v;
      T.modify(1, 1, n, l, r - 1, {v});
    } else {
      cin >> x;
      cout << T.query(1, 1, n, x).add << '\n';
    }
  }
  return 0;
}

区间修改，区间查询

以区间加修改，查询单点值，查询区间和为例，给出如下代码。

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 1;

int a[MAXN];

struct SegTree {
  int sum[MAXN << 2];  // 信息
  int tag[MAXN << 2];  // 区间加懒标记

  int comb(int a, int b) {  // 结点信息合并运算
    return a + b;
  }

  void build(int o, int l, int r) {
    tag[o] = 0;     // 初始化懒标记
    if (l == r) {
      sum[o] = a[l];  // 初始化
      return ;
    }
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    sum[o] = comb(sum[o << 1], sum[o << 1 | 1]);
  }

  void down(int o, int l, int mid, int r) {
    if (tag[o] > 0) {
      // 下放懒标记给左右儿子区间
      tag[o << 1] += tag[o];
      tag[o << 1 | 1] += tag[o];
      // 计算下放的懒标记对左右儿子区间记录的信息的修改
      sum[o << 1] += tag[o] * (mid - l + 1);
      sum[o << 1 | 1] += tag[o] * (r - mid);
      // 懒标记恢复初始状态
      tag[o] = 0;
    }
  }

  void modify(int o, int l, int r, int ql, int qr, int v) {
    if (ql <= l && r <= qr) {     // 修改查询区间完全包含当前结点区间
      tag[o] += v;                // 更新懒标记 
      sum[o] += v * (r - l + 1);  // 更新区间信息
      return ;
    }
    int mid = (l + r) >> 1;
    down(o, l, mid, r);  // 当前区间可能有懒标记，下放
    if (ql <= mid) {
      modify(o << 1, l, mid, ql, qr, v);
    }
    if (qr > mid) {
      modify(o << 1 | 1, mid + 1, r, ql, qr, v);
    }
    // 由于更新了包含区间的懒标记和信息，因此自下而上更新信息
    sum[o] = comb(sum[o << 1], sum[o << 1 | 1]);  
  }

  int query(int o, int l, int r, int i) {
    if (l == r) {
      return sum[o];
    }
    int mid = (l + r) >> 1;
    down(o, l, mid, r);  // 当前区间可能有懒标记，下放
    return i <= mid ? query(o << 1, l, mid, i) : query(o << 1 | 1, mid + 1, r, i);
  }

  int query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
      return sum[o];
    }
    if (ql > r || qr < l) {
      return 0;
    }
    int mid = (l + r) >> 1;
    down(o, l, mid, r);  // 当前区间可能有懒标记，下放
    return query(o << 1, l, mid, ql, qr) + query(o << 1 | 1, mid + 1, r, ql, qr);
  }
} T;

注意

如果只有单点查询，其实所有的自下而上的更新是都不需要的。

只要递归了某个结点区间，就要将懒标记下方。

区间修改之后要重新自下而上更新。

需要注意的是，down() 中有时候分配给左右儿子的标记并不是相同的，并且给每个被修改查询包含区间的信息也有可能是不同的。

区间修改

当有一定的数学抽象能力时，可以阅读区间修改封装参考资料

部分同学学习线段树后，总是不知道如何实现 down() 函数，以及懒标记打在被包含区间上时的代码。这是因为没有搞清楚懒标记的引入到底对线段树的哪些部分产生了作用。

区间对线段树维护的信息和方法提出了新的要求：

我们需要记录对结点的影响，使得这个影响后续能够扩散给儿子。每个结点所记录的影响信息称为懒标记，lazy tag。维护的信息有两种：原始信息（简称信息）和懒标记。
懒标记需要能够作用于信息，即结点信息可以看做为元素 x，懒标记可以抽象的看做成一个函数映射 x \gets f(x)
一个区间可以多次先后地、按顺序地叠加懒标记。例如对结点信息 x 叠加两次懒标记，f_2(f_1(x))，对结点先做懒标记 f_1 的运算，再将运算结果做 f_2 的运算。
如果记录一个结点先后的所有懒标记，然后依次运算，显然时空复杂度很高。因此我们需要想办法将 f_2(f_1(x)) 变为一个新的、只进行一次运算的函数 g(x)。
当区间没有被修改时，我们需要一个恒等映射 f(x) = x。

简单来说，我们需要维护：

信息和懒标记
信息之间的合并运算
懒标记之间的函数复合运算
懒标记对信息的函数运算
信息单位元，恒等映射

这些运算之间需要满足何种关系，请阅读参考资料。

下面代码为封装版本代码。

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 1;

struct Node {  // 结点信息
  // 填写代码部分
};

struct Tag {  // 懒标记
  // 填写代码部分
  bool operator==(const Tag &i) const {  // 判断懒标记相等
    // 填写代码部分
  }
};

struct SegTree {
  Node dat[MAXN << 2];
  Tag tag[MAXN << 2];
  Node E = {/*填写代码部分*/};  // 单位元
  Tag I = {/*填写代码部分*/};   // 恒等映射

  Node comb(const Node &dat1, const Node &dat2) {  // 信息合并运算
    // 填写代码部分
    return {};
  }

  Tag F(const Tag &tag1, const Tag &tag2) {  // 懒标记函数复合运算
    // 填写代码部分
    return {};
  }

  Node f(const Tag &tag, const Node &dat) {  // 懒标记对信息的函数运算
    // 填写代码部分
  }

  void build(int o, int l, int r) {
    // 初始化懒标记填写代码部分
    if (l == r) {
      // 初始化信息填写代码部分
      return;
    }
    int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    dat[o] = comb(dat[o << 1], dat[o << 1 | 1]);
  }

  void down(int o) {  // 懒标记下放
    if (tag[o] == I) {
      return;
    }
    tag[o << 1] = F(tag[o], tag[o << 1]);
    tag[o << 1 | 1] = F(tag[o], tag[o << 1 | 1]);
    dat[o << 1] = f(tag[o], dat[o << 1]);
    dat[o << 1 | 1] = f(tag[o], dat[o << 1 | 1]);
    tag[o] = I;
    /*
    需要注意的是，有时候分配给左右儿子的标记并不是相同的
    */
  }

  void modify(int o, int l, int r, int ql, int qr, Tag t) {  // 区间修改
    if (ql <= l && r <= qr) {
      // 需要注意的是，有时候给被包含区间的懒标记是不同的
      tag[o] = F(t, tag[o]);
      dat[o] = f(t, dat[o]);
      return;
    }
    int mid = (l + r) >> 1;
    down(o);
    if (ql <= mid) {
      modify(o << 1, l, mid, ql, qr, t);
    }
    if (qr > mid) {
      modify(o << 1 | 1, mid + 1, r, ql, qr, t);
    }
    dat[o] = comb(dat[o << 1], dat[o << 1 | 1]);
  }

  Node query(int o, int l, int r, int i) {  // 单点查询
    if (l == r) {
      return dat[o];
    }
    int mid = (l + r) >> 1;
    down(o);
    return i <= mid ? query(o << 1, l, mid, i) : query(o << 1 | 1, mid + 1, r, i);
  }

  Node query(int o, int l, int r, int ql, int qr) {  // 区间查询
    if (ql <= l && r <= qr) {
      return dat[o];
    }
    if (ql > r || qr < l) {
      return E;
    }
    int mid = (l + r) >> 1;
    down(o);
    return comb(query(o << 1, l, mid, ql, qr), query(o << 1 | 1, mid + 1, r, ql, qr));
  }
} T;

int main() {
  return 0;
}

如何得到需要维护的信息和标记

分析流程同单点修改线段树部分，不过引入新的懒标记以后也要重新进行分析流程。

需要注意，在分析流程中，有三种情况要考虑：

信息的合并
懒标记的复合
懒标记对信息的函数映射

找到维护的信息顺便要求出所维护信息的计算方法。