## 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[40] stores: array[40] + array[39] ... + array[32] (8 positions) array[32] stores: array[32] + array[31] ... + array[1] (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[40] 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[32] has information of 32 items, and We are done!

So cummulative data of array[1...40] = array[40] + array[32] 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 Description
`FenwickTree​(int size)`
• ### Method Summary

All Methods
Modifier and Type Method 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 java.lang.Object

`clone, equals, 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