Assume you have an array of length n initialized with all 0's and are given k update operations.
Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex ... endIndex](inclusive) with inc.
Return the modified array after all k operations were executed.

Example
A = [0, 0, 0, 0, 0]
Update:
[1,3,2] => A = [0, 2, 2, 2, 0]
[2,4,3] => A = [0, 2, 5, 5, 3]
[0,2,-2] => A = [-2,0, 3, 5, 3]

Result = [-2,0, 3, 5, 3]

Solution
  1. The straightforward solution would be for each update query (start, end, k) we for from start -> end and update a[i] += k.

Runtime: O(m*n) (m: number of query, n: A.size())

  1. A better way is to utilize the prefix sum: S[i] = sum(A[0]...A[i]), S[i] will have information of subarray A[0..i].

For each query (start, end, k), we update:

  • A[start] += k. So when calculate S[i] (i >= start), all S[i] will be added k.
  • Because we only want to add up to end item, we have to update A[end+1] -= k so when calculate S[i] (i > end),k is subtracted from all S[i].
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        vector<int> a = vector<int>(length, 0);
        for(auto update: updates) {
            int u = update[0];
            int v = update[1];
            int val = update[2];
            a[u]+=val;
            if (v+1 < length) a[v+1]-=val;
        }        
        for(int i = 1; i < length; i++)
            a[i] += a[i-1];
        return a;
    }

Runtime: O(m + n)

Application
  1. https://leetcode.com/problems/meeting-rooms-ii/
    We can think of this problem as follow: let time[i]: number of meeting at time i, for each meeting [start, end], we add 1 to time[i], where start <= i < end. The problem become, find max(time[i]) after we update for all meetings. Now we can apply the abobe technique for solving this problem, just use a map<int, int> instead of an array, because the array need to be update now is a continuous range (time), not a concrete array.
    int minMeetingRooms(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](vector<int> x, vector<int> y) {
            return x[0] < y[0];
        });

	    map<int, int> a;
	    for(auto meeting: intervals) {
	        int s = meeting[0];
	        int e = meeting[1];
	        a[s]++;
	        a[e]--;
	    }

	    int count = 0;
	    int res = 0;
	    for(auto pair: a) {
	        count += pair.second;
	        res = max(res, count);
	    }
	    return res;
    }

Runtime: O(2n*log(2n))

Simillaly, we can do following problems:

2.https://leetcode.com/problems/my-calendar-ii
3.https://leetcode.com/problems/my-calendar-iii