一维差分

可以在 \(O(1)\) 的时间内对区间 \([l, r]\) 中的每个数加上一个数 \(c\)。

例题1

代码实现

参考实现

C++JavaPython

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],b[N];
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i]-a[i-1];
    }
    for(int i=1;i<=m;i++){
        int l,r,d;
        scanf("%d%d%d",&l,&r,&d);
        b[l]+=d;
        b[r+1]-=d;
    }
    for(int i=1;i<=n;i++){
        b[i]=b[i-1]+b[i];
        printf("%d ",b[i]);
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        long[] a = new long[n + 1];
        long[] b = new long[n + 2];

        for (int i = 1; i <= n; i++) {
            a[i] = in.nextLong(); // 输入序列
            b[i] = a[i] - a[i - 1];
        }

        while (m-- > 0) {
            int l = in.nextInt();
            int r = in.nextInt();
            int d = in.nextInt();
            b[l] += d;
            b[r + 1] -= d;
        }

        for (int i = 1; i <= n; i++) {
            b[i] = b[i - 1] + b[i];
            System.out.print(b[i] + " ");
        }
        System.out.println();
    }
}

import os
import sys
n,m=map(int,input().split())
a=[0]+list(map(int,input().split()))+[0]#len=n+2
b=[0]*(n+2)
for i in range(1,n+1):
    b[i]=a[i]-a[i-1]#差分方程

for i in  range(0,m):
    l,r,d=map(int,input().split())
    b[l]+=d
    b[r+1]-=d

for i in range(1,n+1):
    b[i]=b[i]+b[i-1]
    print(b[i],end=" ")

例题2

自建OJ：最少操作次数

代码实现

参考实现

C++JavaPython

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+5;

int a[N],b[N];

int main(){
    int n;
    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i]-a[i-1];
    }

    ll ans=0;

    for(int i=1;i<=n;i++){
        if(b[i]>0){
            ans+=b[i];
        }
    }

    cout<<ans-1;

    return 0;
}

import java.util.*;

public class Main {

    static final int N=100005;
    static int[] a=new int[N];
    static int[] b=new int[N];

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);

        int n=sc.nextInt();

        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
            b[i]=a[i]-a[i-1];
        }

        long ans=0;

        for(int i=1;i<=n;i++){
            if(b[i]>0){
                ans+=b[i];
            }
        }

        System.out.println(ans-1);
    }
}

n=int(input())
a=[0]+list(map(int,input().split()))
b=[0]*(n+1)

for i in range(1,n+1):
    b[i]=a[i]-a[i-1]

ans=0
for i in range(1,n+1):
    if b[i]>0:
        ans+=b[i]

print(ans-1)

代码实现

一维差分