korayucar
8/18/2016 - 8:37 PM

lgn solution for range sum increment decrement queries over an array of integers. Code can be augmented by adding index value query and ind

lgn solution for range sum increment decrement queries over an array of integers. Code can be augmented by adding index value query and index value setting operations both of which would be lgn ideally.

FenwickTree.java
content_copyfile_download

import java.util.*;

/**
Java Fenwick tree implementation allows index range sum queries of lgn and
index increment decrement operations of lgn.

go here for a good tutorial on the matter

https://www.youtube.com/watch?v=v_wj_mOAlig

*/
public class FenwickTree{

  private static final boolean DEBUG = true;

  int [] elements;

  public FenwickTree(int size){
    elements = new int[size+1];
  }


  public void increment(int index , int value){
    while(index < elements.length){
      elements[index] += value;
      index = incrementByLastSetBit(index);
    }
    printDebug("after increment at index " + index + " by " + value);
  }

  public int getRangeSum(int inclusiveStart , int inclusiveEnd){
    //TODO: check input
    int ret = getPrefixSum(inclusiveEnd) - getPrefixSum(inclusiveStart -1);
    printDebug("Value between index " + inclusiveStart+ " and index " +inclusiveEnd +" (both inclusive) is: " + ret);
    return ret;
  }

  private int getPrefixSum(int inclusiveIndex){
    int result = 0;
    while(inclusiveIndex > 0){
      result += elements[inclusiveIndex];
      inclusiveIndex = removeLastBit(inclusiveIndex);
    }

    return result;
  }

  private int removeLastBit(int original){
    return  (original - 1) & original;
  }

  private int incrementByLastSetBit(int val){
    return val + (val & ( -1*val));
  }

  private void printDebug(String description){
    if(!DEBUG)
    return;
    System.out.println(description);
    System.out.println(Arrays.toString(elements));

  }
  public static void main(String... args){
    FenwickTree tree = new FenwickTree(13);
    for(int i =1 ; i < 4 ; i++){
      tree.increment(4,12);
      tree.increment(5,-3);
      assert tree.getRangeSum(3,8) == 9*i;
    }
  }


}