public class FenwickTree extends Object
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)
Constructor and Description 

FenwickTree(int size) 
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 1indexed

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.

public int rsq(int ind)
TimeComplexity: O(log(n))
ind
 indexpublic int rsq(int a, int b)
TimeComplexity: O(log(n))
a
 left indexb
 right indexpublic void update(int ind, int value)
TimeComplexity: O(log(n))
ind
 indexvalue
 valuepublic int size()
public static void main(String[] args)
The array is 1indexed 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]
args
 the commandline arguments