嘛…稍微复习一下线段树好了…

因为是复习笔记，所以讲的很简略，也只讲了基础的东西，还留了很多坑…

填坑的话…省选后要是没 AFO 再说吧…Latex 炸的有点厉害，去我 Blog 看会好很多：https://xjx885.coding-pages.com/post/pyrz7nPvO/

[HTML_REMOVED]

前言：

$\qquad$ 线段树大概是用的最多的树形数据结构了吧？

$\qquad$ 比起其他数据结构，线段树板子没啥难度，难度下界很低。

$\qquad$ 但因为它可以添加很多区间标记，它的难度上界却又相当高…

$\qquad$ 啧啧......

$~\\$

正文：

$\qquad$ 线段树基础操作（区间加减乘赋值极值和）就不讲了，直接上三道模板题：

$~\\$

• 例题：洛谷 P3372 【模板】线段树 1

• 解析：区间加，区间求和都是基操…

• 代码：

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 1e5 + 10;

  #define int long long

  #define mid ((tree[root].l+tree[root].r)>>1)
  #define lc (tree[root].ls)
  #define rc (tree[root].rs)

  inline int read();

  struct node
  {
      int l, r, ls, rs;
      int delay, sum, siz;
  } tree[N * 2];

  int n, m, rt, tot;
  int d[N];

  void push_up(int root)
  {
      tree[root].sum = tree[lc].sum + tree[rc].sum;
  }

  void push_down(int root)
  {
      if(tree[root].delay)
      {
          int D = tree[root].delay;
          tree[lc].delay += D, tree[rc].delay += D;
          tree[lc].sum += tree[lc].siz * D;
          tree[rc].sum += tree[rc].siz * D;
          tree[root].delay = 0;
      }
  }

  void Creat(int & root, int l, int r)
  {
      root = ++tot, tree[root].siz = r - l + 1;
      tree[root].l = l, tree[root].r = r;
      if(l == r)
          tree[root].sum = d[l];
      else
      {
          Creat(lc, l, mid), Creat(rc, mid + 1, r);
          push_up(root);
      }
  }

  void Add(int root, int l, int r, int key)
  {
      if(tree[root].l >= l && tree[root].r <= r)
      {
          tree[root].delay += key;
          tree[root].sum += key * tree[root].siz;
          return ;
      }

      push_down(root);
      if(r <= mid) Add(lc, l, r, key);
      else if(l > mid) Add(rc, l, r, key);
      else Add(lc, l, mid, key), Add(rc, mid + 1, r, key);

      push_up(root);
  }

  int Sum(int root, int l, int r)
  {
      if(tree[root].l >= l && tree[root].r <= r)
          return tree[root].sum;

      push_down(root);
      if(r <= mid) return Sum(lc, l, r);
      else if(l > mid) return Sum(rc, l, r);
      else return Sum(lc, l, mid) + Sum(rc, mid + 1, r);
  }

  signed main()
  {
      n = read(), m = read();
      for(register int k = 1; k <= n; k++)
          d[k] = read();
      Creat(rt, 1, n);

      for(register int k = 1; k <= m; k++)
      {
          int opt = read(), x = read(), y = read();
          if(opt - 1)
              printf("%lld\n", Sum(rt, x, y));
          else
              Add(rt, x, y, read());
      }

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }

$~\\$

$~\\$

• 例题：洛谷 P3373 【模板】线段树 2

• 解析：上一题的升级版，板子升级后还是板子…

• 代码：

  //调了一个小时...
  //我神仙地敲了个 M(x,y*1ll)
  //展开后就是 x=x*y*1ll%p，直接爆 int Orz...

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 1e5 + 10;

  #define mid ((tree[root].l+tree[root].r)>>1)
  #define lc (tree[root].ls)
  #define rc (tree[root].rs)
  #define M(a,b) (a = a * b % p)
  #define MOD(x) (x = x % p)

  inline int read();

  struct node
  {
      int l, r, ls, rs;
      int delay1, delay2, sum, siz;
  } tree[N * 2];

  int n, m, p, rt, tot;
  int d[N];

  void push_up(int root)
  {
      tree[root].sum = (tree[lc].sum + tree[rc].sum) % p;
  }

  void push_down(int root)
  {
      if(tree[root].delay2 != 1)
      {
          long long D = tree[root].delay2;
          M(tree[lc].delay2, D), M(tree[rc].delay2, D);
          M(tree[lc].delay1, D), M(tree[rc].delay1, D);
          M(tree[lc].sum, D), M(tree[rc].sum, D);
          tree[root].delay2 = 1;
      }
      if(tree[root].delay1)
      {
          long long D = tree[root].delay1;
          tree[lc].delay1 += D, tree[rc].delay1 += D;
          MOD(tree[lc].delay1), MOD(tree[rc].delay1);
          tree[lc].sum += tree[lc].siz * D % p, MOD(tree[lc].sum);
          tree[rc].sum += tree[rc].siz * D % p, MOD(tree[rc].sum);
          tree[root].delay1 = 0;
      }
  }

  void Creat(int & root, int l, int r)
  {
      root = ++tot, tree[root].siz = r - l + 1;
      tree[root].l = l, tree[root].r = r, tree[root].delay2 = 1;
      if(l == r)
          tree[root].sum = d[l];
      else
      {
          Creat(lc, l, mid), Creat(rc, mid + 1, r);
          push_up(root);
      }
  }

  void Add(int root, int l, int r, long long key)
  {
      if(tree[root].l >= l && tree[root].r <= r)
      {
          tree[root].delay1 += key, MOD(tree[root].delay1);
          tree[root].sum += key * tree[root].siz % p, MOD(tree[root].sum);
          return ;
      }

      push_down(root);
      if(r <= mid) Add(lc, l, r, key);
      else if(l > mid) Add(rc, l, r, key);
      else Add(lc, l, mid, key), Add(rc, mid + 1, r, key);

      push_up(root);
  }

  void Mul(int root, int l, int r, long long key)
  {
      if(tree[root].l >= l && tree[root].r <= r)
      {
          M(tree[root].delay2, key);
          M(tree[root].delay1, key);
          M(tree[root].sum, key);
          return ;
      }

      push_down(root);
      if(r <= mid) Mul(lc, l, r, key);
      else if(l > mid) Mul(rc, l, r, key);
      else Mul(lc, l, mid, key), Mul(rc, mid + 1, r, key);

      push_up(root);
  }

  int Sum(int root, int l, int r)
  {
      if(tree[root].l >= l && tree[root].r <= r)
          return tree[root].sum;

      push_down(root);
      if(r <= mid) return Sum(lc, l, r);
      else if(l > mid) return Sum(rc, l, r);
      else return (Sum(lc, l, mid) + Sum(rc, mid + 1, r)) % p;
  }

  signed main()
  {
      n = read(), m = read(), p = read();
      for(register int k = 1; k <= n; k++)
          d[k] = read() % p;
      Creat(rt, 1, n);

      for(register int k = 1; k <= m; k++)
      {
          int opt = read(), x = read(), y = read();
          if(opt == 1)
              Mul(rt, x, y, read() % p);
          else if(opt == 2)
              Add(rt, x, y, read() % p);
          else
              printf("%d\n", Sum(rt, x, y));
      }

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }

$~\\$

$~\\$

• 例题：洛谷 P6242 【模板】线段树 3

• 解析：不知道为啥这题算线段树模板3......这玩意是吉司机线段树…不咋考的知识点…用来完成区间最值操作和区间历史最值操作…有兴趣的可以看洛谷日报，这里不详细讲了。

• 代码：忘了，懒得敲了…

$~\\$

$~\\$

$\qquad$ 模板放完了，下面再放点拓展题。

$~\\$

• 例题：洛谷 P1438 无聊的数列

• 解析：第一眼我看成了李超树…敲到一半才发现是加法…题目不难，抓住等差数列的性质：$a_{i+1}-a_{i}=d$，我们不妨丢弃原始序列，用线段树/树状数组维护其差分序列，这样，加等差数列可以看做区间加，求某个点的值可以看做区间和，裸上线段树就完事了。

• 代码：

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 1e5 + 10;

  #define mid ((tree[root].l+tree[root].r)>>1)
  #define lc (tree[root].ls)
  #define rc (tree[root].rs)

  inline int read();

  struct node
  {
      int l, r, ls, rs;
      int delay, sum, siz;
  } tree[N * 2];

  int n, m, rt, tot;
  int d[N];

  void push_up(int root)
  {
      tree[root].sum = tree[lc].sum + tree[rc].sum;
  }

  void push_down(int root)
  {
      if(tree[root].delay)
      {
          int D = tree[root].delay;
          tree[lc].delay += D, tree[rc].delay += D;
          tree[lc].sum += tree[lc].siz * D;
          tree[rc].sum += tree[rc].siz * D;
          tree[root].delay = 0;
      }
  }

  void Creat(int & root, int l, int r)
  {
      root = ++tot, tree[root].siz = r - l + 1;
      tree[root].l = l, tree[root].r = r;
      if(l == r)
          tree[root].sum = d[l];
      else
      {
          Creat(lc, l, mid), Creat(rc, mid + 1, r);
          push_up(root);
      }
  }

  void Add(int root, int l, int r, int key)
  {
      if(r < l) return ;

      if(tree[root].l >= l && tree[root].r <= r)
      {
          tree[root].delay += key;
          tree[root].sum += key * tree[root].siz;
          return ;
      }

      push_down(root);
      if(r <= mid) Add(lc, l, r, key);
      else if(l > mid) Add(rc, l, r, key);
      else Add(lc, l, mid, key), Add(rc, mid + 1, r, key);

      push_up(root);
  }

  int Sum(int root, int l, int r)
  {
      if(tree[root].l >= l && tree[root].r <= r)
          return tree[root].sum;

      push_down(root);
      if(r <= mid) return Sum(lc, l, r);
      else if(l > mid) return Sum(rc, l, r);
      else return Sum(lc, l, mid) + Sum(rc, mid + 1, r);
  }

  signed main()
  {
      n = read(), m = read();
      for(register int k = 1; k <= n; k++)
          d[k] = read();
      for(register int k = n; k >= 1; k--)
          d[k] = d[k] - d[k - 1];
      Creat(rt, 1, n);

      for(register int k = 1; k <= m; k++)
      {
          int opt = read(), x = read();
          if(opt - 1)
              printf("%d\n", Sum(rt, 1, x));
          else
          {
              int y = read(), z = read(), c = read();
              Add(rt, x + 1, y, c), Add(rt, x, x, z);
              if(y + 1 <= n)Add(rt, y + 1, y + 1, c * (x - y) - z);
          }
      }

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }

$~\\$

$~\\$

$\qquad$ 上面那题对线段树维护的序列进行了处理，使得原本不好维护的序列变得可维护，在解决复杂线段树问题时，这是一种很重要的思路。

$\qquad$ 下面这道例题则着重于对线段树本身进行扩展，即各种标记的设计，上传，下放，冲突。

$~\\$

• 例题：洛谷 P2572 [SCOI2010]序列操作（超级玛（码）丽（力）

• 解析：操作有点多，我们先从询问看起（$3,4$操作）， $3$ 操作比较好说，我们只要维护区间中 $0/1$ 任意一个的数量就好，$0,1$ 操作可以直接打 $Lazy$ 标记，$2$ 操作可以额外维护一个 $reverse$ 标记。$4$ 操作时线段树中常见的最长连续段问题，我们可以维护区间内最长连续段长度，包含区间左端点的最长连续段长度，包含区间右端点的最长连续段长度，然后合并即可，但麻烦的地方在于 $2$ 操作会直接影响到 $4$ 操作的维护过程…所以我们不仅得维护 $1$ 的最长连续段长度，还要维护 $0$ 的最长连续段长度......也是相当复杂了。

• 总结：我们得维护区间 $0$（或者 $1$） 数目（与 $0,1,3$操作有关），$Lazy$ 标记（与 $0,1,3$ 操作有关），$reverse$ 标记（与 $2,3,4$ 操作有关），区间 $0$ 和 $1$ 的最长连续段与左右最长连续段的长度（与 $0,1,2,4$ 操作有关）。

• 代码：我调了两个小时来着…

  #include <queue>
  #include <vector>
  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <algorithm>

  using namespace std;

  const int N = 1e5 + 10;

  #define mid ((tree[root].l+tree[root].r)>>1)
  #define lc (tree[root].ls)
  #define rc (tree[root].rs)

  inline int read();

  struct node
  {
      int l, r, ls, rs, siz;
      int d, num_1, rev;
      int l1, r1, max1;
      int l0, r0, max0;
  } tree[N * 2];

  int n, m, rt, tot;
  int d[N];

  void push_up(int root)
  {
      tree[root].num_1 = tree[lc].num_1 + tree[rc].num_1;
      tree[root].l0 = (tree[lc].l0 == tree[lc].siz ? tree[lc].siz + tree[rc].l0 : tree[lc].l0);
      tree[root].l1 = (tree[lc].l1 == tree[lc].siz ? tree[lc].siz + tree[rc].l1 : tree[lc].l1);
      tree[root].r0 = (tree[rc].r0 == tree[rc].siz ? tree[rc].siz + tree[lc].r0 : tree[rc].r0);
      tree[root].r1 = (tree[rc].r1 == tree[rc].siz ? tree[rc].siz + tree[lc].r1 : tree[rc].r1);
      tree[root].max0 = max(max(tree[lc].max0, tree[rc].max0), tree[lc].r0 + tree[rc].l0);
      tree[root].max1 = max(max(tree[lc].max1, tree[rc].max1), tree[lc].r1 + tree[rc].l1);
  }

  void push_down(int root)
  {
      if(tree[root].rev)
      {
          if(tree[lc].d != -1) tree[lc].d ^= 1;
          if(tree[rc].d != -1) tree[rc].d ^= 1;
          swap(tree[lc].l0, tree[lc].l1), swap(tree[rc].l0, tree[rc].l1);
          swap(tree[lc].r0, tree[lc].r1), swap(tree[rc].r0, tree[rc].r1);
          swap(tree[lc].max0, tree[lc].max1), swap(tree[rc].max0, tree[rc].max1);
          tree[lc].num_1 = tree[lc].siz - tree[lc].num_1;
          tree[rc].num_1 = tree[rc].siz - tree[rc].num_1;

          tree[root].rev = 0;
          tree[lc].rev ^= 1, tree[rc].rev ^= 1;
      }
      if(tree[root].d != -1)
      {
          if(tree[root].d == 1)
          {
              tree[lc].l0 = tree[lc].r0 = tree[lc].max0 = 0;
              tree[lc].l1 = tree[lc].r1 = tree[lc].max1 = tree[lc].siz;
              tree[rc].l0 = tree[rc].r0 = tree[rc].max0 = 0;
              tree[rc].l1 = tree[rc].r1 = tree[rc].max1 = tree[rc].siz;
              tree[lc].num_1 = tree[lc].siz, tree[rc].num_1 = tree[rc].siz;
          }
          else
          {
              tree[lc].l0 = tree[lc].r0 = tree[lc].max0 = tree[lc].siz;
              tree[lc].l1 = tree[lc].r1 = tree[lc].max1 = 0;
              tree[rc].l0 = tree[rc].r0 = tree[rc].max0 = tree[rc].siz;
              tree[rc].l1 = tree[rc].r1 = tree[rc].max1 = 0;
              tree[lc].num_1 = tree[rc].num_1 = 0;
          }

          tree[lc].d = tree[rc].d = tree[root].d;
          tree[root].d = -1;
      }
  }

  void Creat(int & root, int l, int r)
  {
      root = ++tot, tree[root].siz = r - l + 1;
      tree[root].l = l, tree[root].r = r, tree[root].d = -1;

      if(l == r)
          if(d[l])
              tree[root].l1 = tree[root].r1 = tree[root].max1 = tree[root].num_1 = 1;
          else
              tree[root].l0 = tree[root].r0 = tree[root].max0 = 1;
      else
          Creat(lc, l, mid), Creat(rc, mid + 1, r), push_up(root);
  }

  void Change(int root , int l, int r, int key)
  {
      if(tree[root].l >= l && tree[root].r <= r)
      {
          tree[root].d = key;
          if(key)
          {
              tree[root].l1 = tree[root].r1 = tree[root].max1 = tree[root].num_1 = tree[root].siz;
              tree[root].l0 = tree[root].r0 = tree[root].max0 = 0;
          }
          else
          {
              tree[root].l1 = tree[root].r1 = tree[root].max1 = tree[root].num_1 = 0;
              tree[root].l0 = tree[root].r0 = tree[root].max0 = tree[root].siz;
          }
          return ;
      }

      push_down(root);
      if(r <= mid) Change(lc, l, r, key);
      else if(l > mid) Change(rc, l, r, key);
      else Change(lc, l, mid, key), Change(rc, mid + 1, r, key);
      push_up(root);
  }

  void Reverse(int root, int l, int r)
  {
      if(tree[root].l >= l && tree[root].r <= r)
      {
          tree[root].rev ^= 1;
          if(tree[root].d != -1) tree[root].d ^= 1;
          swap(tree[root].l0, tree[root].l1);
          swap(tree[root].r0, tree[root].r1);
          swap(tree[root].max0, tree[root].max1);
          tree[root].num_1 = tree[root].siz - tree[root].num_1;

          return ;
      }

      push_down(root);
      if(r <= mid) Reverse(lc, l, r);
      else if(l > mid) Reverse(rc, l, r);
      else Reverse(lc, l, mid), Reverse(rc, mid + 1, r);
      push_up(root);
  }

  int Query1(int root, int l, int r)
  {
      if(tree[root].l >= l && tree[root].r <= r)
          return tree[root].num_1;

      push_down(root);
      if(r <= mid) return Query1(lc, l, r);
      else if(l > mid) return Query1(rc, l, r);
      else return Query1(lc, l, mid) + Query1(rc, mid + 1, r);
  }

  struct Node
  {
      int Max, lmax, rmax;

      Node(int a, int b, int c)
      {
          Max = a, lmax = b, rmax = c;
      }
      Node() { }
  };

  Node Query2(int root, int l, int r)
  {
      if(tree[root].l >= l && tree[root].r <= r)
          return Node(tree[root].max1, tree[root].l1, tree[root].r1);

      push_down(root);
      if(r <= mid) return Query2(lc, l, r);
      else if(l > mid) return Query2(rc, l, r);
      else
      {
          Node A = Query2(lc, l, mid), B = Query2(rc, mid + 1, r);
          int MAX = max(A.Max, max(B.Max, A.rmax + B.lmax));
          int LMAX = (A.lmax == mid - l + 1 ? A.lmax + B.lmax : A.lmax);
          int RMAX = (B.rmax == r - mid ? B.rmax + A.rmax : B.rmax);
          return Node(MAX, LMAX, RMAX);
      }
  }

  signed main()
  {
      n = read(), m = read();
      for(register int k = 1; k <= n; k++)
          d[k] = read();
      Creat(rt, 1, n);

      for(register int k = 1; k <= m; k++)
      {
          int opt = read(), l = read() + 1, r = read() + 1;
          if(opt == 0) Change(rt, l, r, 0);
          else if(opt == 1) Change(rt, l, r, 1);
          else if(opt == 2) Reverse(rt, l, r);
          else if(opt == 3) printf("%d\n", Query1(rt, l, r));
          else printf("%d\n", Query2(rt, l, r).Max);
      }

      return 0;
  }

  inline int read()
  {
      int fh = 1, x = 0, ch = '~';

      while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
      while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

      return x * fh;
  }

$~\\$

$~\\$

$\qquad$ 上面那题难吗？一点都不难（所有操作都是基操）......然而在比赛中能调出线段树解法的人，大概非神即欧了吧…

$\qquad$ 下面简单介绍几个线段树的拓展模型和应用。

$~\\$

$\qquad$ 猫树：本来应该先讲 ZKW线段树 的，但我一般不用那玩意…

$\qquad$ 猫树是一种维护满足结合律且要求快速合并的信息的静态线段树。

$\qquad$ 一般线段树在建树时进行了 $O(n)$ 次合并操作，猫树则需进行 $O(nlogn)$ 次，一般线段树查询时要进行 $O(logn)$ 次合并操作，猫树只需要 $O(1)$ 次，也就是说，查询操作会快很多（其实也还好来着）。

$\qquad$ 猫树的核心思路是：对区间 $[L,R]$，预处理出 $Sum_l(i)=\sum\limits_{j=i}^{mid}d(j),i\in[L,mid]$（$d(j)$ 表示序列中 $j$ 位置的元素的值），同理预处理出 $Sum_r(i)=\sum\limits_{j=mid+1}^{i}d(j),i\in[mid+1,R]$，这样，如果有询问 $[l,r] \subset [L,R]$，我们可以把它视为 $[l,mid] \cup (mid,r]$，如果我们可以高效率地合并 $[l,mid]$ 和 $(mid,r]$，就可以更快地解决问题。

$\qquad$ 这要求信息不能修改且满足结合律。比如说区间和，区间最值等等，它们均可以 $O(1)$ 合并完成。

$\qquad$ 现在还剩下两个问题：

$\qquad$ 第一，怎么预处理 $Sum_{i/j}$ 数组。很显然，我们直接在 $creat$ 操作的时候对每个节点算出来就好了，画个图，可以直观感受到，存储它的空间复杂度是 $O(nlogn)$ 的，时间复杂度也如此。

$\qquad$ 第二，怎么确定每个 $[l,r]$ 区间对应哪个 $[L,R]$ 区间，我们是要保证 $mid$ 在 $[l,r]$ 里面的。这里直接给一个结论：我们设 $[l,l]$ 对应的节点编号为 $x$， $[r,r]$ 对应节点为 $y$，则满足条件的一个 $[L,R]$ 对应节点层数为 $log_2x-log_2{(x \oplus y)}$，预处理出 $log_2i$ 即可 $O(1)$ 算出。

$~\\$

$~\\$

• 例题：SP1043 GSS1 - Can you answer these queries I

• 解析：猫树模板题，$M$ 要是再大一点就可以卡死普通线段树了。求的是最大连续子段和，可以看成左右两边的最大和和过中点的最大和的并。

• 代码：

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 4e5 + 10;

inline int read();

#define mid ((l+r)>>1)

int n, n0, m, tot;
int d[N], cs[N], num[N], lg[N];
int Max[22][N][2], Cmax[22][N][2];
//最大和，过中点的最大和

void creat(int root, int l, int r, int C)
{
    cs[root] = C;
    if(l == r)
    {
        num[l] = root;
        return ;
    }
    else creat(root << 1, l, mid, C + 1), creat(root << 1 | 1, mid + 1, r, C + 1);

    Cmax[C][mid][0] = d[mid], Cmax[C][mid + 1][1] = d[mid + 1];
    for(register int k = mid - 1; k >= l; k--) Cmax[C][k][0] = Cmax[C][k + 1][0] + d[k];
    for(register int k = mid - 1; k >= l; k--) Cmax[C][k][0] = max(Cmax[C][k + 1][0], Cmax[C][k][0]);
    for(register int k = mid + 2; k <= r; k++) Cmax[C][k][1] = Cmax[C][k - 1][1] + d[k];
    for(register int k = mid + 2; k <= r; k++) Cmax[C][k][1] = max(Cmax[C][k - 1][1], Cmax[C][k][1]);
    Max[C][mid][0] = Max[C][mid][1] = d[mid];
    for(register int k = mid - 1; k >= l; k--) Max[C][k][0] = Max[C][k + 1][0] > 0 ? Max[C][k + 1][0] + d[k] : d[k];
    for(register int k = mid - 1; k >= l; k--) Max[C][k][0] = max(Max[C][k][0], Max[C][k + 1][0]);
    for(register int k = mid + 1; k <= r; k++) Max[C][k][1] = Max[C][k - 1][1] > 0 ? Max[C][k - 1][1] + d[k] : d[k];
    for(register int k = mid + 1; k <= r; k++) Max[C][k][1] = max(Max[C][k][1], Max[C][k - 1][1]);
}

signed main()
{
    n0 = read();
    for(register int k = 1; k <= n0; k++)
        d[k] = read();

    //把元素个数化为 2 的整数次幂
    for(n = 1; n < n0; n <<= 1);
    for(register int k = 2; k <= n * 2; k++)
        lg[k] = lg[k >> 1] + 1;
    creat(1, 1, n, 1);

    m = read();
    for(register int k = 1; k <= m; k++)
    {
        int x = read(), y = read();
        if(x == y)
        {
            printf("%lld\n", d[x]);
            continue;
        }

        int P = lg[num[x]] - lg[num[x] ^ num[y]];
        printf("%lld\n", max(Cmax[P][x][0] + Cmax[P][y][1], max(Max[P][x][0] , Max[P][y][1])));
    }

    return 0;
}

inline int read()
{
    int fh = 1, x = 0, ch = '~';

    while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}

$~\\$

$~\\$

$\qquad$ 扫描线：虚拟一条坐标系上不存在的不断移动的线来求矩形周长面积并等数据的方法。

$~\\$

• 例题：洛谷 P5490 【模板】扫描线

• 解析：对于扫描线问题，我们一般虚拟一条不存在的横向直线，并让它从最低处向上一格一格地移动，当它经过某个矩形的下边时，我们把这个矩形左右覆盖的这一段的点的标记++，我们每次移动时，需要在最终答案上加上当前被标记的点的数量，当我们经过某个矩形的上边时，我们把这一段的标记数量–，扫完后答案就出来了。画画图就可以验证这个方法的正确性，周长也可以用类似的方法解决（还要加一根从左往右的扫描线）。

• 关于本题线段树：两种方案，一种是维护区间最小值和最小值个数，区间修改时打上 $Lazy$ 标记。这种方案又慢又难处理。另一种方案是根据本题特殊性：每一个 $[l,r]+1$ 都一定对应一个 $[l,r]-1$，所以我们可以直接维护区间内元素整体标记次数和区间内标记的数的总数，后者用 $push_up$ 维护，前者不用管就好。

• 代码：

#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

#define mid ((tree[root].l+tree[root].r)>>1)
#define lc (tree[root].ls)
#define rc (tree[root].rs)

inline int read();

struct node
{
    int l, r, ls, rs;
    int d, num, siz;
} tree[N * 4];

struct Node
{
    int x1, y1, x2, y2;
} Q[N];

struct NODE
{
    int d, wz, type;
    NODE(int a, int b, int c)
    {
        d = a, wz = b, type = c;
    }
    NODE() {}

    bool operator < (const NODE & other ) const
    {
        return d < other.d;
    }
} ls[N * 2];

int n, tot, rt, ys_x[N * 2], ys_y[N * 2];
vector <NODE > ques[N * 2];

void LS()
{
    for(register int k = 1; k <= n; k++)
    {
        ls[k].d = Q[k].x1, ls[k].wz = k, ls[k].type = 1;
        ls[k + n].d = Q[k].x2, ls[k + n].wz = k, ls[k + n].type = 2;
    }
    sort(ls + 1, ls + 1 + 2 * n);
    tot = 0, ls[0].d = -1;
    for(register int k = 1; k <= n * 2; k++)
    {
        if(ls[k].d != ls[k - 1].d) ys_x[++tot] = ls[k].d;
        if(ls[k].type == 1) Q[ls[k].wz].x1 = tot;
        else Q[ls[k].wz].x2 = tot;
    }

    for(register int k = 1; k <= n; k++)
    {
        ls[k].d = Q[k].y1, ls[k].wz = k, ls[k].type = 1;
        ls[k + n].d = Q[k].y2, ls[k + n].wz = k, ls[k + n].type = 2;
    }
    sort(ls + 1, ls + 1 + 2 * n);
    tot = 0, ls[0].d = -1;
    for(register int k = 1; k <= n * 2; k++)
    {
        if(ls[k].d != ls[k - 1].d) ys_y[++tot] = ls[k].d;
        if(ls[k].type == 1) Q[ls[k].wz].y1 = tot;
        else Q[ls[k].wz].y2 = tot;
    }
}

void push_up(int root)
{
    if(tree[root].d) tree[root].num = tree[root].siz;
    else tree[root].num = tree[lc].num + tree[rc].num;
}

void creat(int & root, int l, int r)
{
    root = ++tot, tree[root].siz = ys_y[r] - ys_y[l];
    tree[root].l = l, tree[root].r = r;
    if(l != r - 1)
        creat(lc, l, mid), creat(rc, mid, r);
}

void change(int root, int l, int r, int key)
{
    if(tree[root].l >= l && tree[root].r <= r)
    {
        tree[root].d += key, push_up(root);
        return ;
    }

    if(r <= mid) change(lc, l, r, key);
    else if(l >= mid) change(rc, l, r, key);
    else change(lc, l, mid, key), change(rc, mid, r, key);
    push_up(root);
}

long long query(int root, int l, int r)
{
    if(tree[root].l >= l && tree[root].r <= r)
        return tree[root].num;

    if(r <= mid) return query(lc, l, r);
    else if(l >= mid) return query(rc, l, r);
    else return query(lc, l, mid) + query(rc, mid, r);
}

long long ans;

signed main()
{
    n = read();
    for(register int k = 1; k <= n; k++)
    {
        Q[k].x1 = read(), Q[k].y1 = read();
        Q[k].x2 = read(), Q[k].y2 = read();
    }
    LS(), tot = 0, creat(rt, 1, 2 * n);

    for(register int k = 1; k <= n; k++)
    {
        ques[Q[k].x1].push_back(NODE(Q[k].y1, Q[k].y2, 1));
        ques[Q[k].x2].push_back(NODE(Q[k].y1, Q[k].y2, -1));
    }

    for(register int k = 1; k <= 2 * n; k++)
    {
        ans += query(rt, 1, 2 * n) * (ys_x[k] - ys_x[k - 1]);
        for(int i = 0; i < (int )ques[k].size(); i++)
        {
            int y1 = ques[k][i].d, y2 = ques[k][i].wz, key = ques[k][i].type;
            change(rt, y1, y2, key);
        }
    }

    printf("%lld", ans);

    return 0;
}

inline int read()
{
    int fh = 1, x = 0, ch = '~';

    while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}

$~\\$

$~\\$

$\qquad$ 权值线段树：维护权值上的区间信息的线段树。

$\qquad$ 权值线段树和普通线段树没有本质区别，其本质是线段树维护桶（而不是维护序列），它常用来解决整体第 $K$ 大问题（支持修改，询问整个序列中第 $K$ 大的数是多少）。

$\qquad$ 这个不太好找例题，就不放例题了。

$~\\$

$\qquad$ 主席树：即可持久化线段树。

$\qquad$ 从定义上看，主席树可以回溯历史版本…所以我们常用主席树模拟可持久化线性数据结构。但主席树本身一般不用来回溯历史版本，我们常用它来求解静态区间第 $K$ 大问题（权值线段树只能解决整体第 K 大问题）。

$\qquad$ 其具体思路之类的，我的另一篇文章有讲…这里就不赘述了。

$~\\$

• 例题：洛谷 P3834 【模板】可持久化线段树 （主席树）

• 解析：模板题要什么解析。

• 代码：

#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

#define mid ((l+r)>>1)
#define lc (tree[root].ls)
#define rc (tree[root].rs)

inline int read();

struct node
{
    int ls, rs, siz;
} tree[N << 6];

int rt[N], tot, n, m, len, d[N], ys[N];
pair <int , int > P[N];

void creat(int & root, int l, int r)
{
    root = ++tot;
    if(l != r)
        creat(lc, l, mid), creat(rc, mid + 1, r);
}

int update(int root, int l, int r, int key)
{
    int Root = ++tot;
    tree[Root].ls = lc, tree[Root].rs = rc;
    tree[Root].siz = tree[root].siz + 1;
    if(l == r) return Root;

    if(key <= mid)
        tree[Root].ls = update(lc, l, mid, key);
    else
        tree[Root].rs = update(rc, mid + 1, r, key);
    return Root;
}

int query(int Root, int root, int l, int r, int key)
{
    if(l == r) return ys[l];

    int Lc = tree[Root].ls, Size = tree[Lc].siz - tree[lc].siz;
    if(Size >= key) return query(Lc, lc, l, mid, key);
    else return query(tree[Root].rs, rc, mid + 1, r, key - Size);
}

signed main()
{
    n = read(), m = read();
    for(register int k = 1; k <= n; k++)
        d[k] = read(), P[k] = make_pair(d[k], k);

    sort(P + 1, P + 1 + n), P[0].first = 114514;
    for(register int k = 1; k <= n; k++)
    {
        if(P[k].first != P[k - 1].first)
            ys[++tot] = P[k].first;
        d[P[k].second] = tot;
    }

    len = tot, tot = 0, creat(rt[0], 1, len);
    for(register int k = 1; k <= n; k++)
        rt[k] = update(rt[k - 1], 1, len, d[k]);

    for(register int k = 1; k <= m; k++)
    {
        int l = read(), r = read(), K = read();
        printf("%d\n", query(rt[r], rt[l - 1], 1, len, K));
    }

    return 0;
}

inline int read()
{
    int fh = 1, x = 0, ch = '~';

    while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();

    return x * fh;
}

$~\\$

$~\\$

$\qquad$ 主席树可以拓展出不少算法…像可持久化 01-trie 就完全可以按主席树思路来写，可持久化数组和可持久化并查集甚至可以直接用主席树模拟出来。

$\qquad$ Kth 问题还有更进化的版本，比如说区间动态 $Kth$ 这个得拿树套树做…不咋考，这里不复习了。

$\qquad$ 那么就这样吧…线段树一直是热门考点来着，但接下来也要复习其它数据结构了。