Range Sum Segment Tree

RangeSumSegmentTree.java

public class RangeSumSegmentTree {
  private int n = 0;
  private int[] tree;
  public RangeSumSegmentTree(int[] a) {
    n = a.length;
    tree = new int[2*n];
    for(int i = 0; i < n; ++i) {
      update(i, a[i]);
    }
  }
  public void update(int i, int val) {
    int k = n + i;
    tree[k] = val;
    for(k /= 2; k >= 1; k /= 2) {
      // left is always 2k, right is 2k+1
      tree[k] = tree[2*k] + tree[2*k + 1];
    }
  }
  public int sum(int i, int j) {
    i += n;
    j += n;
    int sum = 0;
    while(i <= j) {
      // odd are right children
      if(i%2 == 1) {
          sum += tree[i++];    
      }
      // even are left children
      if(j%2 == 0) {
          sum += tree[j--];
      }
      i /= 2;
      j /= 2;
    }
    return sum;
  }
}