Codeforces Codeforces Round #359 (Div. 1) - D. Kay and Eternity

Problem Statement:
http://codeforces.com/contest/685/problem/D

Summary:
In an infinite 2D array, there are n < 10^5 cells (x[i], y[i]) with value 1, where -1e9 <= x[i], y[i] <= 1e9. The rest of the cells are 0. For each m = 1 to n, compute the number of squares with dimension k x k (k <= 300), with the property that each of those squares has exactly m non-zero cells in it.

Data Structure: Fenwick Tree and Range Update

Something led me to read up on Fenwick Tree (a.k.a Binary Indexed Tree). There are lots of great tutorials that explain what this data structure is, and how it is useful. A google search is all you need. I would like to write up some short discussion on the tree, and also about a technique that is used to allow this tree to support range updates.

Data Structure for Frequent Range Updates

Given an update operation as following: from index i to index j, we add p to each array[i]. What kind of data structure that can support this operation efficiently?

Of course segment tree and fenwick tree does this well in \(O(N\lg{N})\) complexity for building the tree, \(O(\lg{N})\) for updates (insertion), and \(O(\lg{N})\) for processing search queries. However, what if we have a use case where we do updates very very frequently, like 99% of the time?

Two days ago I've discovered this data structure while reading on some people's code, and I'm not really sure whether there is a standard way to call it. The data structure I am about to present here does the updates in O(1) (yeap) but to do a search query we have at worst O(N) at each time. But the simplicity is really striking.

We use an array to keep track on the updates information, call this mark[]. For each updates in the form of (p, i, j), we do:
1. mark[j] += p
2. mark[i-1] -= p
And this information suffices to show that we intent to add p to each and every cell in i to j.

How do we process the information when we need to do a retrieval of data? Once the need arise, we do a one sweep operation from i = N to 1: mark[i-1] += mark[i]
Then each mark[i] represent how much values we already added to element i throughout the updating process!