动态区间特殊值——线段树的简单应用

• 问题引入
• 简单介绍
• 功能详情
• 碎碎念

问题引入

很多地方写的是区间最值问题，感觉区间特殊值更好一些，区间gcd、前缀和都可以，问题描述大致就是给出一个数组，要求给出询问区间的特殊值，当然求和之类的可以用树状数组解决，但是最大、最小等等特殊值是不能转化为前缀和用树状数组解决的，因此用线段树解决

简单介绍

如图所示，线段树简单来说就是把数组分成很多条线段（区间），最大的区间是整个数组，最小的区间是每个元素本身，每个区间每次分割一般，因此查询和修改的时间都是nlog n，大致也可以推测线段树是从底层向顶层更新建立而来，单点修改这点倒是挺像建树；同时也可以看到线段树的空间消耗挺多的，根据证明的话，线段树的空间一般开N*4，下面的案例给出的是求区间和

功能详情

• 数据存储：结构体

  struct node {
    int nSum, xtag, ytag;
  }
  

• 杂函数：一些功能辅助函数，直接给出
  • 求当前节点的左右儿子

    ll getL(int id) {return id<<1;}
    ll getR(int id) {return (id<<1)|1;}
    

  • 求和

    ll sum(ll x, ll y) {return x+y;}
    

  • 利用儿子节点更新本身

    void update(int id) {
      t[id].nSum = sum(t[getL(id)].nSum, t[getR(id)].nSum);
    }
    

• 建树：递归建树，而后更新
  大致说一下我自己的理解哈，算法的预处理也只能从已知推向未知，刚开始的时候，我们肯定是不知道任何一个大区间的信息的，知道的只有最小区间的信息，因此只能由下向上更新特殊值，下面给出一般代码

  void build(int idx, int lt, int rt) {
      //到达最小区间，开始赋值
      if(lt == rt) t[idx].nSum = a[lt];
      else {
          int mid = (lt + rt) >> 1;
          //递归左右子树
          build(getL(idx), lt, mid);
          build(getR(idx), mid+1, rt);
          //利用儿子节点更新父节点
          update(idx);
      }
  }
  

• 单点修改：就是自顶向下确定位置后，再自底向上更新
  单点修改的时间复杂度是nlog n，和建树倒是有些类似，先向下遍历，直到到达修改的单点，将其值做相应修改，由于单点修改比较好看，直接给出代码

  void change(int idx, int lt, int rt, int cidx, int add) {
      //如果到了叶子结点，说明是修改的点，修改即可
      if(lt == rt) t[idx].nSum += add;
      else {
          int mid = (lt+rt) >> 1;
          //不是叶子结点，则向两边裂开，在左区间就向左边裂开，右区间就向右边裂开
          if(cidx <= mid) change(getL(idx), lt, mid, cidx, add);
          else change(getR(idx), mid+1, rt, cidx, add);
          //更新父亲结点
          update(idx);
      }
  }
  

• 区间修改：利用lazy_tag技术，简单来说就是拖延症，能拖就拖，不到用的时候就不更新
  区间修改其实我刚开始看的时候还挺迷糊的，什么lazy_tag标记，什么标记下沉，玄乎，其实看明白了也挺好理解的，区间修改其实挺符合本人的为人处事的思想准则的——拖延症(bushi)，和他名字也很贴切，lazy——就是尽量做更少的操作。首先第一件事，每一次区间修改操作，如果我们费劲费时的去修改，但是最后并没有查询到这个区间，这是不是一种浪费。第二个，要是我们对一个区间先后做了+x-x的操作，这无疑也是一种浪费，因为这并没有产生任何的效果，但是假如我们从一开始就知道这个区间要+x-x，是否可以减少操作次数。lazy_tag给出的操作就是能少操作就少操作，对于每一次区间修改操作，先将其放到较大的区间内，保证能以尽量少的操作完成修改的意思，之后要求更细化的操作再将操作细化，即下沉操作。这里给出一个例子，以最上面的图为例，假如我们要对区间[2, 5]同时加x，那么最开始的操作就是将区间[2, 2], [3, 3], [4, 5]的区间的tag标记加上x，只有后面的查询或者修改操作涉及到[4, 5]的子区间时才会将[4, 5]区间内的tag下沉，否则就一直不动。
  准确来说，对于查询操作，如果当前区间太大要细分，那么首先将tag值下沉；对于区间修改操作，如果当前区间完完整整被包含在修改区间，由于是自大区间向小区间下降，所以第一个遇到的被包含区间一定是符合“懒惰操作”特性的，要是要细分区间，同样要将当前区间的tag下沉后继续操作。

  void pushdown(int idx, int lt, int rt) {
      if(t[idx].tag) {
          int mid = (lt+rt) >> 1;
          //注意，在修改的时候都是加等，因为该位置本来就可能有值
          t[getL(idx)].tag += t[idx].tag, t[getR(idx)].tag += t[idx].tag;
          t[getL(idx)].nSum += t[idx].tag * (mid - lt + 1);
          t[getR(idx)].nSum += t[idx].tag * (rt - mid);
          //下沉后就将改点的tag归零
          t[idx].tag = 0;
      }
  }
  
  void modify(int idx, int lt, int rt, int ml, int mr, int k) {
      //如果当前区间完全被包含，对其做tag标记，同时修改答案
      if(lt >= ml && rt <= mr) t[idx].nSum += (rt - lt + 1) * k ,t[idx].tag += k;
      else {
          int mid = (lt+rt) >> 1;
          pushdown(idx, lt, rt);
          if(mr <= mid) modify(getL(idx), lt, mid, ml, mr, k);
          else if(ml > mid) modify(getR(idx), mid+1, rt, ml, mr, k);
          else {
              modify(getL(idx), lt, mid, ml, mid, k);
              modify(getR(idx), mid+1, rt, mid+1, rt, k);
          }
          update(idx);
      }
  }
  

• 区间查询：分类讨论，递归分解区间而来
  区间查询，就是将大区间划分为小区间的答案汇总，是一种的化整为散的思想，对于当前区间，如果查询区间的答案都在左区间，那么就递归处理左区间，如果查询区间都在右区间，那么就递归处理右区间，要是两边都有，就处理递归处理两边

  int query(int idx, int lt, int rt, int ql, int qr) {
     int ans = 0;
     if(lt == ql && rt == qr) ans += t[idx].nSum;
     else {
         int mid = (lt+rt) >> 1;
         //区间修改和单点修改查询的唯一区别，就在于区间修改的查询之前要将tag向下沉
         pushdown(idx, lt, rt);
         if(qr <= mid) ans += query(getL(idx), lt, mid, ql, qr);
         else if(ql > mid) ans += query(getR(idx), mid+1, rt, ql, qr);
         else ans += sum(query(getL(idx), lt, mid, ql, mid), query(getR(idx), mid+1, rt, mid+1, rt));
     }
     return ans;
  }
  

碎碎念

线段树值得吐槽的点其实在我做的时候很有感触，但是由于本人是一个记忆力不太棒的人，所以只能记得部分了

• 线段树的空间是消耗很大的，注意开N * 4
• 关于每个点的管理区间可以放在结构体内，也可以像上面的写法，每次传参，我不是很想写到结构体内的原因是赋值麻烦，取出来更麻烦，不如传参
• 好的，结构体有结构体的坏处，传参自然也有，就是，我不是一个记忆力很好的人，有的时候会忘记我传过来的这两个玩意是什么意思，emmm
• 当然，上面是我的问题，还有一个问题，就是函数的参数稍多，而且有两对都是表示区间的值，因此写的时候注意不要写混，不然很不容易找出来（别问我为什么有这个体会，吐），这里给出的方法就是好好命名，比如管理区间就是正常的lt、rt，查询区间就是ql、qr，修改区间就是ml、m这类的，总而言之，就是根据自己的命名习惯来，不弄混就行
• 更新其实是一个容易忽略的操作，想想什么时候更新，什么时候不更新，更新的原因是啥
• tag标签可以多个，根据题目要什么操作，对于几个基本操作，两个参数就够了，*xtag + ytag，加减乘除加上一个变换，反正这几个是够用的