on
on

【区间求和问题】差分入门

Author:

LeetCode1109 航班预定统计

这里有n个航班，它们分别从1到n进行编号。
有一份航班预定表bookings，表中第i条预订记录bookings[i] = [first_i, last_i, seats_i]，意味着从first_i到last_i的每个航班上预定了seats_i个座位。
请你返回一个长度为n的数组answer，其中answer[i]是航班i上预定的座位总数。

基本分析

  • 数组不变，区间查询：前缀和、树状数组、线段树；
  • 数组单点修改，区间查询：树状数组、线段树；
  • 数组区间修改，单点查询：差分、线段树；
  • 数组区间修改，区间查询：线段树；

上述总结是对于一般性而言的，对标的是模板问题。但存在经过一些额外操作，对问题进行转化，从而使用别的解决方案求解的情况。
例如某些问题，我们可以先对原数组进行差分，然后使用树状数组，也能解决区间修改问题。
或者使用多个数组来维护多个指标，从而实现类似线段树的持久化标记操作。

差分

「差分」可以看做是求「前缀和」的逆向过程。
对于一个「将区间 [l,r] 整体增加一个值 v 」的操作，我们可以将差分数组c的影响看成两部分：

  • 对c[l] += v: 由于差分是「前缀和」的逆向过程，这个操作对于将来的查询而言，是对于所有的下表大于等于 l 的文职都增加了值 v 。
  • 对c[r+1] -= v; 由于我们期望只对 [l,r]产生影响，因此需要对下标大于等于r的位置进行减值操作，抵消影响。
class Solution {
    public int[] corpFlightBookings(int[][] bs, int n) {
        int[] c = new int[n + 1];
        for (int[] bo : bs) {
            int l = bo[0] - 1, r = bo[1] - 1, v = bo[2];
            c[l] += v;
            c[r + 1] -= v;
        }
        int[] ans = new int[n];
        ans[0] = c[0];
        for (int i = 1; i < n; i++) {
            ans[i] = ans[i - 1] + c[i];
        }
        return ans;
    }
}

时间复杂度：令「bs」长度为 m，预处理查分数组的复杂度为 O(m)；构造答案复杂度为 O(n)。整体复杂度为 O(m+n)
空间复杂度：O(n)

线段树

「基本分析」中，我们发现几乎所有的「区间求和」问题都可以使用线段树解决。但是线段树代码很长，且常数很大，实际表现不算好。线段树实现如下：

class Solution {
    class Node {
        int l, r, v, add;
        Node(int _l, int _r) {
            l = _l; r = _r;
        }
    }
    int N = 20009;
    Node[] tr = new Node[N * 4];
    void pushup(int u) {
        tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v;
    }
    void pushdown(int u) {
        int add = tr[u].add;
        tr[u << 1].v += add;
        tr[u << 1].add += add;
        tr[u << 1 | 1].v += add;
        tr[u << 1 | 1].add += add;
        tr[u].add = 0;
    }
    void build(int u, int l, int r) {
        tr[u] = new Node(l, r);
        if (l != r) {
            int mid = l + r >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
        }
    }
    void update(int u, int l, int r, int v) {
        if (l <= tr[u].l && tr[u].r <= r) {
            tr[u].v += v;
            tr[u].add += v;
        } else {
            pushdown(u);
            int mid = tr[u].l + tr[u].r >> 1;
            if (l <= mid) update(u << 1, l, r, v);
            if (r > mid) update(u << 1 | 1, l, r, v);
            pushup(u);
        }
    }
    int query(int u, int l, int r) {
        if (l <= tr[u].l && tr[u].r <= r) {
            return tr[u].v;
        } else {
            pushdown(u);
            int mid = tr[u].l + tr[u].r >> 1;
            int ans = 0;
            if (l <= mid) ans += query(u << 1, l, r);
            if (r > mid) ans += query(u << 1 | 1, l, r);
            return ans;
        }
    }
    public int[] corpFlightBookings(int[][] bs, int n) {
        build(1, 1, n);
        for (int[] bo : bs) {
            update(1, bo[0], bo[1], bo[2]);
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = query(1, i + 1, i + 1);
        }
        return ans;
    }
}

时间复杂度: 建树复杂度为O(n)，其余操作复杂度为 O(log n)。对于本题，整体复杂度为O(mlogn + nlogn)
空间复杂度：O(n)

参考自https://mp.weixin.qq.com/s/_DzsKXy2FQPkuAgz2yfBVQ

Categories: Leetcode