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 subarrayA[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

- 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())

- 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

- 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