Fenwick.java

class Fenwick{
    
    private final int n;
    private int[] tree;
    private int[] array;
    
    //initialise tree
    public Fenwick(int n) {
        this.n = n + 1;
        this.tree = new int[this.n];
        this.array = new int[this.n];
    }
    
    public Fenwick(int[] values) {

        this.n = values.length + 1;
        this.array = new int[n];
                
        for(int i = 1; i < this.n; i++){
            array[i] = values[i-1];
        }

        tree = array.clone();

        for (int child = 1; child < n; child++) {
            int parent = child + RSB(child);
            
            if (parent < n) {
                tree[parent] += tree[child];
            }
        }
    }
    
    /*
    update values of array[index] to val
    delta = newVal - previousVal
    (zero based indexing in argument)
    */
    public void update(int index, int val){
        index += 1;
        int delta = val - array[index];
        array[index] = val;
        
        int pos =  index;
        while(pos < n){
            tree[pos] += delta;
            pos += RSB(pos);
        }
    }
    
    /*
    increment value of array[index] by delta
    (zero based indexing in argument)
    */
    public void increment(int index, int delta){
        index += 1;
        array[index] += delta;
        
        int pos =  index;
        while(pos < n){
            tree[pos] += delta;
            pos += RSB(pos);
        }
    }
        
    /*
    find prefixSum till index
    (one based indexing in argument)
    */
    public int prefixSum(int index) {
        int ans = 0;
        
        while (index != 0) {
            ans += tree[index];
            index -= RSB(index); 
        }
        
        return ans;
    }
    
    /*
    returns the rightmost set bit
    */
    private static int RSB(int i) {

        return i & -i;
    }
    
}

class FenwickRangeQueryPointUpdate extends Fenwick{
    FenwickRangeQueryPointUpdate(int n){
        super(n);
    }
    
    FenwickRangeQueryPointUpdate(int [] values){
        super(values);
    }
    /*
    range query from index l to r
    (zero based indexing in argument)
    */
    public int query(int left, int right){
        return prefixSum(right + 1) - prefixSum(left);
    }
}

class FenwickPointQueryRangeUpdate{
    private Fenwick fTree;
    private int length_arr;
        
    //initialise tree
    FenwickPointQueryRangeUpdate(int n, int [] array){
        this.fTree = new Fenwick(n);
        this.length_arr = n;
               
        for(int i = 0; i < n; i++){
            int delta = array[i];
            
            fTree.increment(i, delta);
            if(i + 1 < length_arr){
                fTree.increment(i + 1, -delta);
            }
        }     
    }
    
    /*
    increment the values from index l to r by delta
    (zero based indexing in argument)
    */
    public void range_update(int left, int right, int delta){
        fTree.increment(left, delta);
        if(right + 1 < length_arr){
            fTree.increment(right + 1, -delta);
        }
        
    }
    
    /*
    return value of index
    (zero based indexing in argument)
    */
    public int point_query(int index){
        return fTree.prefixSum(index + 1);
    }
    
}

class FenwickRangeQueryRangeUpdate{
    private Fenwick fTree1, fTree2;
    private int length_arr;
    
    //intialise 2 Fenwick Trees
    public FenwickRangeQueryRangeUpdate(int n, int [] array){
        this.fTree1 = new Fenwick(n);
        this.fTree2 = new Fenwick(n);
        this.length_arr = n;
        
        for(int i = 0; i < n; i++){
            int delta = array[i];
            
            fTree1.increment(i, delta);
            if(i + 1 < length_arr)
            {
                fTree1.increment(i + 1, -delta);
            }

            fTree2.increment(i, delta*(i - 1));
            if(i + 1 < length_arr)
            {
                fTree2.increment(i + 1, -delta*i);
            }
        }
    }
    
    /*
    increment the values from index l to r by delta
    (zero based indexing in argument)
    */
    public void increment(int left, int right, int delta){            
        fTree1.increment(left, delta);
        if(right + 1 < length_arr)
        {
            fTree1.increment(right + 1, -delta);
        }
        
        fTree2.increment(left, delta*(left - 1));
        if(right + 1 < length_arr)
        {
            fTree2.increment(right + 1, -delta*right);
        }
    }
    
    /*
    range query from index l to r
    (zero based indexing in argument)
    */
    public int query(int left, int right){
        return prefixSum(right + 1) - prefixSum(left);
    }
    
    /*
    find prefixSum till index
    (one based indexing in argument)
    */
    public int prefixSum(int index){
        return fTree1.prefixSum(index) * (index - 1) - fTree2.prefixSum(index);
    }
}