Fenwick tree for sum and max

public class FenwickTree {

  // T[i] += value
  public static void add(int[] t, int i, int value) {
    for (; i < t.length; i |= i + 1)
      t[i+= value;
  }

  // sum[0..i]
  public static int sum(int[] t, int i) {
    int res = 0;
    for (; i >= 0; i = (i & (i + 1)) 1)
      res += t[i];
    return res;
  }

  ///////////////////////////////////////////////////

  // T[i] = max(T[i], value)
  public static void set(int[] t, int i, int value) {
    for (; i < t.length; i |= i + 1)
      t[i= Math.max(t[i], value);
  }

  // max[0..i]
  public static int max(int[] t, int i) {
    int res = Integer.MIN_VALUE;
    for (; i >= 0; i = (i & (i + 1)) 1)
      res = Math.max(res, t[i]);
    return res;
  }

  // Usage example
  public static void main(String[] args) {
    int[] t = new int[10];
    add(t, 01);
    add(t, 9, -2);
    System.out.println(-== sum(t, 9));
  }
}
Comments