edu.princeton.cs.algs4

## Class FenwickTree

• Object
• edu.princeton.cs.algs4.FenwickTree

• ```public class FenwickTree
extends Object```
Created by ricardodpsx@gmail.com on 4/01/15.

In `Fenwick Tree` structure We arrange the array in an smart way to perform efficient range queries and updates. The key point is this: In a fenwick array, each position "responsible" for storing cumulative data of N previous positions (N could be 1) For example: array stores: array + array ... + array (8 positions) array stores: array + array ... + array (32 positions)

But, how do you know how much positions a given index is "responsible" for?

To know the number of items that a given array position 'ind' is responsible for We should extract from 'ind' the portion up to the first significant one of the binary representation of 'ind' for example, given ind == 40 (101000 in binary), according to Fenwick algorithm what We want is to extract 1000(8 in decimal).

This means that array has cumulative information of 8 array items. But We still need to know the cumulative data bellow array[40 - 8 = 32] 32 is 100000 in binnary, and the portion up to the least significant one is 32 itself! So array has information of 32 items, and We are done!

So cummulative data of array[1...40] = array + array Because 40 has information of items from 40 to 32, and 32 has information of items from 32 to 1

Memory usage: O(n)

Author:
Ricardo Pacheco
• ### Constructor Summary

Constructors
Constructor and Description
`FenwickTree(int size)`
• ### Method Summary

All Methods
Modifier and Type Method and Description
`static void` `main(String[] args)`
Read the following commands: init n Initializes the array of size n all zeroes set a b c Initializes the array with [a, b, c ...] rsq a b Range Sum Query for the range [a,b] up i v Update the i position of the array with value v.
`int` `rsq(int ind)`
Range Sum query from 1 to ind ind is 1-indexed
`int` ```rsq(int a, int b)```
Range Sum Query from a to b.
`int` `size()`
`void` ```update(int ind, int value)```
Update the array at ind and all the affected regions above ind.
• ### Methods inherited from class Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### FenwickTree

`public FenwickTree(int size)`
• ### Method Detail

• #### rsq

`public int rsq(int ind)`
Range Sum query from 1 to ind ind is 1-indexed

Time-Complexity: O(log(n))

Parameters:
`ind` - index
Returns:
sum
• #### rsq

```public int rsq(int a,
int b)```
Range Sum Query from a to b. Search for the sum from array index from a to b a and b are 1-indexed

Time-Complexity: O(log(n))

Parameters:
`a` - left index
`b` - right index
Returns:
sum
• #### update

```public void update(int ind,
int value)```
Update the array at ind and all the affected regions above ind. ind is 1-indexed

Time-Complexity: O(log(n))

Parameters:
`ind` - index
`value` - value
• #### size

`public int size()`
• #### main

`public static void main(String[] args)`
Read the following commands: init n Initializes the array of size n all zeroes set a b c Initializes the array with [a, b, c ...] rsq a b Range Sum Query for the range [a,b] up i v Update the i position of the array with value v. exit

The array is 1-indexed Example: set 1 2 3 4 5 6 rsq 1 3 Sum from 1 to 3 = 6 rmq 1 3 Min from 1 to 3 = 1 input up 1 3 [3,2,3,4,5,6]

Parameters:
`args` - the command-line arguments