线段树差分及其应用

简述概念和应用

  所谓的差分,其实就是后一项与前一项的差,对于第一项而言,(a[0] = 0) 。设数组 (a[~]={1,9,3,5,2}) ,那么差分数组(t[~]={1,8,-6,2,-3}) ,即 (t[i]=a[i]-a[i-1]) ,那么,

[a[i]=t[1]+…+t[i]
]

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

例题一 求差分最值

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

#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("%.2lfn",tem);

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

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]);
}

(Code)

#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("%.2lfn",tem);
        }
    }
    return 0;
}

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

例题二 求最大公因数

NC26255 小阳的贝壳
  这题要求最大公因数和差分最值,最值上一题已经求过了,这最大公因数怎么维护出来呢?而且修改是区间修改的,这貌似也增加了维护最大公因数的难度。我们分开思考,如果只有 (1)(2) 两种操作,区间加和差分是很好维护的,只需要在区间起始位置和终止位置加 (1) 处加上对应值即可(例如我们要原数组 ([2,3]) 区间加上 (4) ,首先是要修改差分数组上的 (t[2] +4), 然后还要修改 (t[4]-4) ,这也是很好理解的,毕竟 ([2,3]) 区间比其他区间突出了一块,整体提高了 (4) ,而其他的区间的差分关系并没有被改变)。
  我们接着思考最大公因数的求法,无非就是辗转相除法和更相减损术,诶,这更相减损术有点差分的意味了。根据更相减损术,有:

[gcd(a,b) = gcd(a,|b-a|)
]

  我们想办法让他和差分联系起来。设原数组为 (A) ,差分数组为 (T) ,则有:

[begin{aligned}
gcd(A_1,A_2,A_3) & = gcd(A_1,gcd(A_2,A_3)) &= gcd(A_1,A_2,|A_3-A_2|)&=gcd(A_1,|A_2-A_1|,|A_3-A_2|)&=gcd(A_1,|T_2|,|T_3|)
end{aligned}
]

  拓展到多个整数的情况,对于区间 ([i,j]),有:

[begin{aligned}
gcd(A_i,A_i+1,···,A_j)&=gcd(A_i,|T_{i+1}|,|T_{i+2}|,···,|T_j|) &=gcd(sum_{k=1}^{i}T_k,|T_{i+1}|,|T_{i+2}|,···,|T_j|)
end{aligned}
]

  这样,我们通过维护差分数组 (T)区间和,区间绝对值最大值,区间最大公因数三个信息就可以做出这道题了。有思路的可以开始做了,代码并不难,只是注意什么值不取绝对值,什么值取绝对值
  我的代码里有一个求 (gcd) 函数(百度的),如果是自己写记得要特判可能会除0的情况。还有一个办法是调用 (<algorithm>) 库里的 (__gcd) 的函数。

(Code):

#include<bits/stdc++.h>
using namespace std;
#define For(i,sta,en) for(int i = sta;i <= en;i++)
#define speedUp_cin_cout ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define mid (l+r)/2
#define ls now<<1
#define rs now<<1|1
const int maxn = 1e5+5;
inline int Gcd(int a,int b){
    if(a == 0) return b;
    if(b == 0) return a;
    while(b^=a^=b^=a%=b);
    return a;
}
int a[maxn],n,m,cha[maxn]; //a为原数组,cha为差分数组
//线段树节点
struct node{
    int sum,gcd,gap;//区间和,最大公因数,最大差的绝对值
}t[maxn<<2];

void pushup(int now){
    t[now].sum = t[ls].sum + t[rs].sum;      //直接加
    t[now].gcd = Gcd(t[ls].gcd,t[rs].gcd);      //两边取最大公约数
    t[now].gap = max(t[ls].gap,t[rs].gap);     //两边取最大差
}

void build(int now,int l,int r){
    if(l == r) {
        t[now].sum = cha[l];
        t[now].gcd = abs(cha[l]);     //取绝对值
        t[now].gap = abs(cha[l]);     //取绝对值
        return;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(now);
}

void update(int now,int l,int r,int pos,int value){
    if(l == r) {
        t[now].sum = cha[l];
        t[now].gcd = abs(cha[l]);
        t[now].gap = abs(cha[l]);
        return;
    }
    if(pos <= mid) update(ls,l,mid,pos,value);
    else update(rs,mid+1,r,pos,value);
    pushup(now);
}

int queryGap(int now,int l,int r,int x,int y){
    if(x <= l && r <= y) return t[now].gap;
    int ans = 0;
    if(x <= mid) ans = max(ans,queryGap(ls,l,mid,x,y));
    if(y > mid) ans = max(ans,queryGap(rs,mid+1,r,x,y));
    return ans;
}

int querySum(int now,int l,int r,int x,int y){
    if(x <= l && r <= y) return t[now].sum;
    int ans = 0;
    if(x <= mid) ans += querySum(ls,l,mid,x,y);
    if(y > mid) ans += querySum(rs,mid+1,r,x,y);
    return ans;
}

int queryGcd(int now,int l,int r,int x,int y){
    if(x <= l && r <= y) return t[now].gcd;
    int ans = 0;
    if(x <= mid) ans = Gcd(ans,queryGcd(ls,l,mid,x,y));
    if(y > mid) ans = Gcd(ans,queryGcd(rs,mid+1,r,x,y));
    return ans;
}

int main(){
    speedUp_cin_cout
    cin>>n>>m;
    For(i,1,n) cin>>a[i],cha[i] = a[i] - a[i-1];
    build(1,1,n);
    int op,x,y,v;
    For(i,1,m){
        cin>>op>>x>>y;
        if(op == 1) {
            cin>>v;
            cha[x] += v;   //注意要修改一下查分数组,和我写法有关
            update(1,1,n,x,v);
            if(y < n) {        //如果不是最后一个还要修改一个单点
                cha[y+1] -= v;
                update(1,1,n,y+1,-v);
            }
        }else if(op == 2) cout<<queryGap(1,1,n,x+1,y)<<endl;  //操作2
        else cout<<Gcd(querySum(1,1,n,1,x),queryGcd(1,1,n,x+1,y))<<endl;  //操作3
    }
    return 0;
}

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

本站资源均源自网络,若涉及您的版权、知识产权或其他利益,请附上版权证明邮件告知。收到您的邮件后,我们将在72小时内删除。
若下载资源地址错误或链接跳转错误请联系站长。站长q:770044133。

» 线段树差分及其应用

发表评论

免登录下载网,提供全网最优质的资源集合!