更好的阅读体验

简述概念和应用

  所谓的差分，其实就是后一项与前一项的差，对于第一项而言， 。设数组 ，那么差分数组 ，即 ,那么，
  差分在线段树和树状数组上应用很广泛。关于树状数组的差分可以用来解决“区间修改，单点查询”的问题，在我上一篇博客讲树状数组入门时有分析，题目是P3368 【模板】树状数组 2。而对于线段树，我们可以考虑对差分数组进行区间维护，比如维护差分数组的区间最大值，即原数组对应区间相邻元素的最大差值。

求差分最值

NC14402 求最大值
  这道题首先要将问题转化，我们不能直接维护这个最大值。如果把问题放到一个二维坐标系，数组下标是横坐标，那么原数组对应的值是纵坐标，这题就是求两点之间最大斜率。画图就可以知道这个最大斜率只可能出现在相邻的两个点之间。问题就变简单了，由上面的结论，我们只要维护出差分数组的区间最大值即可。注意，这个时候线段树的叶子结点变成了原数组的相邻两点的差，不是原数组的某个值。
  我们再来看题目要求的修改方式，是单点修改。那么一个点改变就会改变差分数组中的两个点（如果不是第一个点或者最后一个点的话，这两点需特判）。那么，我们的思路就是建立一棵差分数组作为最底层的线段树（这题并不用懒标记），每次修改就要修改最底层的两个点。来看一下建树操作，注意树根节点的管辖的范围是 的，因为 题目要求 ,即 。按照这个思路就可以自己打代码了，如果觉得细节上还有所欠缺可以继续往下看。

#define ls now<<1
#define rs now<<1|1
#define mid (l+r)/2
int  t[maxn<<2],n,m,num[maxn];

void build(int now,int l,int r){
    if(l == r) {t[now] = num[l] - num[l - 1];return;}
    build(ls,l,mid);
    build(rs,mid+1,r);
    t[now] = max(t[ls],t[rs]);
}

  注意这道题是修改一下就查询一下，查询的最大值其实就已经保留在线段树根节点了。按照我们之前说的，修改要修改线段树中两个叶子结点，并且特判是不是第一个点和后一个点。主函数中部分代码而下：

      scanf ("%d%d", &pos, &value);
      num[pos] = value;             //原数组修改
      if(pos > 1) update(1,2,n,pos,num[pos] - num[pos - 1]);   //如果不是第一个点
      if(pos < n) update(1,2,n,pos+1,num[pos + 1] - num[pos]);  //如果不是最后一个点
      double tem = t[1];
      printf("%.2lf\n",tem);

  最后是修改操作，和普通线段树修改差不多，注意这里不需要懒标记，也就没有 操作了。

void update(int now,int l,int r,int pos,int value){
    if(l == r) {
        t[now] = value;
        return;
    }
    if(pos <= mid) update(ls,l,mid,pos,value);
    else  update(rs,mid+1,r,pos,value);
    t[now] = max(t[ls],t[rs]);
}

：

#include<bits/stdc++.h>
using namespace std;
#define For(i,sta,en) for(int i = sta;i <= en;i++)
#define ls now<<1
#define rs now<<1|1
#define mid (l+r)/2
const int maxn = 2e5+11;
int  t[maxn<<2],n,m,num[maxn];

void build(int now,int l,int r){
    if(l == r) {t[now] = num[l] - num[l - 1];return;}
    build(ls,l,mid);
    build(rs,mid+1,r);
    t[now] = max(t[ls],t[rs]);
}

void update(int now,int l,int r,int pos,int value){
    if(l == r) {
        t[now] = value;
        return;
    }
    if(pos <= mid) update(ls,l,mid,pos,value);
    else  update(rs,mid+1,r,pos,value);
    t[now] = max(t[ls],t[rs]);
}

int main(){
    while(~scanf ("%d", &n)){
        For(i,1,n) scanf ("%d", num+i);
        build(1,2,n);  //注意建树范围，从2到n
        scanf ("%d", &m);int pos,value;
        For(i,1,m){
            scanf ("%d%d", &pos, &value);
            num[pos] = value;             //原数组修改
            if(pos > 1) update(1,2,n,pos,num[pos] - num[pos - 1]);   //如果不是第一个点
            if(pos < n) update(1,2,n,pos+1,num[pos + 1] - num[pos]);  //如果不是最后一个点
            double tem = t[1];
            printf("%.2lf\n",tem);
        }
    }
    return 0;
}

  最后提醒一下，这题在牛客网同一份代码有时 最后三个点，有时只占用总限制内存大小的一半就 了，如果出现这种神奇的情况，多交几次就过了（可能是评测机异常或者测试数据随机？我称之为玄学）。

  希望对你理解有所帮助，如果有不清楚的的地方欢迎和我讨论o(*^▽^*)┛。