FenwickTree (Algorithms 4/e)

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 Static Methods Instance Methods Concrete 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