博客

1109. 航班预订统计

【差分+前缀和】

class Solution {

    // 差分+前缀和 3:47. 4

    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] pre = new int[n + 1];
        for(var k: bookings){
            pre[k[0] - 1] += k[2];
            pre[k[1]] -= k[2];
        }
        int[] ans = new int[n];
        for(var i = 0; i < n; i++){
            if(i == 0) ans[i] = pre[i];
            else ans[i] = pre[i] + ans[i - 1];
        }
        return ans;
    }
}

【差分+树状数组】

这里简单分析一下，树状数组是用来求前缀和的，如果把差分（新增变化量，末尾减少量）存在树状数组中，就可以直接查询前缀和了。

class Solution {

    // 差分+树状数组 3:53 6

    int[] tree;
    int n;

    int lowbit(int x){
        return x & -x;
    }

    void add(int x, int val){
        while(x <= n){
            tree[x] += val;
            x += lowbit(x);
        }
    }

    int ask(int x){
        int ret = 0;
        while(x > 0){
            ret += tree[x];
            x -= lowbit(x);
        }
        return ret;
    }

    public int[] corpFlightBookings(int[][] bookings, int n) {
        this.n = n;
        tree = new int[n + 2];
        for(var b: bookings){
            add(b[0], b[2]);
            add(b[1] + 1, -b[2]);
        }
        int[] ans = new int[n];
        for(var i = 0; i < n; i++){
            ans[i] = ask(i + 1);
        }
        return ans;
    }
}

【差分+线段树】

class Solution {

    // 差分+线段树 4:02 42

    int[] f, a;
    int n;

    void build(int k, int l, int r){
        if(l == r) f[k] = a[l - 1];
        else{
            int mid = (l + r) >>> 1;
            k <<= 1;
            build(k, l, mid);
            build(k, mid + 1, r);
            f[k >>> 1] = f[k] + f[k + 1];
        }
    }

    void add(int k, int l, int r, int x, int y){
        f[k] += y;
        if(l == r) return ;
        int mid = (l + r) >>> 1;
        k <<= 1;
        if(x > mid) add(k + 1, mid + 1, r, x, y);
        else add(k, l, mid, x, y);
    }

    int ask(int k, int l, int r, int x, int y){
        if(l == r) return f[k];
        else if(l == x && r == y) return f[k];
        int mid = (l + r) >>> 1;
        k <<= 1;
        if(x > mid) return ask(k + 1, mid + 1, r, x, y);
        if(y <= mid) return ask(k, l, mid, x, y);
        return ask(k, l, mid, x, mid) + ask(k + 1, mid + 1, r, mid + 1, y);
    }

    public int[] corpFlightBookings(int[][] bookings, int n) {
        int m = n + 1;
        f = new int[m * 4 + 1];
        for(var b: bookings){
            add(1, 1, m, b[0], b[2]);
            add(1, 1, m, b[1] + 1, -b[2]);
        }
        int[] ans = new int[n];
        for(var i = 0; i < n; i++){
            ans[i] = ask(1, 1, m, 1, i + 1);
        }
        return ans;
    }
}