# 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 is always equal to orig.

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 - 1] += b;            if (b < n) res[b] -= b;        }        for (int i = 1; i < n; ++i)            res[i] += res[i - 1];        return res;    }}`