Fenwick Trees

Fenwick Trees

Overall Explanation

Fenwick Trees, or BITs, are a efficient way to dynamically modify array elements and access their prefix sums. It uses the fact that any number can be converted into a unique binary representation to achieve an O(logN) complecity for instructions. Although Fenwick trees are trees in concept, in practice they are implemented as an implicit data structure using a flat array analogous to implementations of a binary heap. Given an index in the array representing a vertex, the index of a vertex's parent or child is calculated through bitwise operations on the binary representation of its index. Each element of the array contains the pre-calculated sum of a range of values, and by combining that sum with additional ranges encountered during an upward traversal to the root, the prefix sum is calculated. When a table value is modified, all range sums which contain the modified value are in turn modified during a similar traversal of the tree. The range sums are defined in such a way that both queries and modifications to the table are executed in asymptotically equivalent time ( O(logN) in the worst case).

The initial process of building the Fenwick tree over a table of values runs in O(n) time. Other efficient operations include locating the index of a value if all values are positive, or all indices with a given value if all values are non-negative. Also supported is the scaling of all values by a constant factor in O(n) time.

A Fenwick tree is most easily understood by considering a one-based array. Each element whose index i is a power of 2 contains the sum of the first i elements. Elements whose indices are the sum of two (distinct) powers of 2 contain the sum of the elements since the preceding power of 2. In general, each element contains the sum of the values since its parent in the tree, and that parent is found by clearing the least-significant bit in the index.

To find the sum up to any given index, consider the binary expansion of the index, and add elements which correspond to each 1 bit in the binary form.

For example, say one wishes to find the sum of the first eleven values. Eleven is 1011 in binary. This contains three 1 bits, so three elements must be added: 1000, 1010, and 1011. These contain the sums of values 1–8, 9–10, and 11, respectively.

To modify the eleventh value, the elements which must be modified are 10112, 11002, 100002, and all higher powers of 2 up to the size of the array. These contain the sums of values 11, 9–12, and 1–16, respectively. The maximum number of elements which may need to be updated is limited by the number of bits in the size of the array.

Summary: Lower Bits

The Lower Bit of a number is a crucial factor in how a Fenwick tree is formed from an index. It can be given through x&-x.

Summary: Querying Sum

When querying for the sum of the first x numbers, we sum up the values of index x in the Fenwick array and then recusively do for x minus its lower bit. This only goes right into an array. It can be efficiently achieved through this code:

int sum(int x)
{
    int res=0;
    while (x>=1)
    {
        res+=c[x];
        x-=lb(x);
    }
    return res;
}
where c is the Fenwick array and lb is the lower bit function.

Summary: Updating Value

To update value x in the Fenwick array, we must update index x itself. Then, we increment x by the lower bit of x and repeat, until x is larger than the size of the array.

void update(int x)
{
    while (x<=Mx)
    {
        c[x]++;
        x+=lb(x);
    }
}

Choppy Prefix Sums Continued

Dynamic Sum Arrays / BITs

Dynamic Sum Arrays

Motive

We have an array of 50000 integers. We are also given 50000 commands, either of type Q or type C. Q-type commands, or queries, given x, are to return the sum of the first x numbers in the array. C-type commands increments the value of a given index, x, in the array by 1. What is the most optimal approach?

Approach 1: Plain Array (Straightforward)

We store the 50000 integers in an array. For every query, we sum up the first x numbers. For a command, we increment the value at x. Make: O(n) Query: O(n) Command: O(1)

Approach 2: Dumb Prefix Summing

For every C-type command, including initialization, we add 1 to every value beyond x. To query, we simply access index x. Make: O(n^2) Query: O(1) Command: O(n)

Approach 3: Recorded Prefix Summing

In initialization, we keep track of the current cum and add the value to the current sum and then copy the value to the index. Everything else is same as approach 2. Make:O(n) Query: O(1) Command: O(n)

We need something better!

Approach 4: Choppy Prefix Sums

Instead of numbering every number, we only number specific details and benchmarks occurring every N numbers.So, in a command, we only increment every number between x and the next benchmark. After that, we only increment benchmarks. To query, we add the number at index x with the last benchmark. Query: O(1) Command: O(n/x+x)

CONTINUED!

GitHub – testitem

Darren Li

New York City