algo-aha

区间增量更新

• https://leetcode.com/problems/range-addition/

vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
    // 将区间[l,r]的值增加inc，只在区间边界记录变化量：arr[l]+=inc; arr[r+1]-=inc;
    // 然后idx处的值就是前缀和sum(arr[0..idx])
    vector<int> ans(length, 0);
    for (auto &update : updates) {
        int l = update[0], r = update[1], inc = update[2];
        ans[l] += inc;
        if (r + 1 < length) ans[r+1] -= inc;
    }
    // 将ans数组从增量变成前缀和
    for (int i = 1; i < length; i++) {
        ans[i] += ans[i-1];
    }
    return ans;
}

另：如果要支持前缀和的快速更新和查询，可以进一步用线段树或二叉索引树。

各区间的右侧下一个区间

• https://leetcode.com/problems/find-right-interval/

vector<int> findRightInterval(vector<vector<int>>& intervals) {
    map<int, int> mp; // start=>idx
    for (int i = 0; i < intervals.size(); i++) {
        mp[intervals[i][0]] = i;
    }

    vector<int> ans;
    // 每个区间找>=end的下一起点：mp.lower_bound(end)
    for (auto &interval : intervals) {
        auto it = mp.lower_bound(interval[1]);
        ans.push_back(it != mp.end() ? it->second : -1);
    }
    return ans;
}