# Difference Array

# Corporate Flight Bookings

So the idea is that every booking will be update to a range, and for range update, we have a special data structure Difference Array which could handle it in O(1) time.

In a nutshell, a difference array is an seperated array that stores the difference of adjacent elements of the original array. Think of it as the reverse of prefix sum array.

`// original array 1 , 5, 7, 7, 9, 3`

// difference array 1 , 4, 2, 0, 2, -6

Notice that diff[0] is always equal to orig[0].

So how to update to a range of items, e.g. you want to add x to every element in range [start, end], just do this:

`diff[start-1] += x;`

diff[end ] -= x;

In the end, just scan from the begining to the end of the diff array, and you’ll get the final vlaue of each element:

`result[i] = result[i - 1] + diff[i]`

Let’s apply the Difference Array to this specific problem:

`class Solution {`

public int[] corpFlightBookings(int[][] bookings, int n) {

int[] res = new int[n];

for (int[] b : bookings) {

res[b[0] - 1] += b[2];

if (b[1] < n) res[b[1]] -= b[2];

}

for (int i = 1; i < n; ++i)

res[i] += res[i - 1];

return res;

}

}