Binary Indexed Tree (Fenwick Tree)

class NumArray {
  int[] tree; // 1 - based indexing
  int n;

  public NumArray(int[] nums) {
    n = nums.length + 1;
    tree = new int[n];
    for (int i = 0; i < nums.length; i++) {
      update(i, nums[i]);
    }
  }

  public void update(int k, int newVal) {
    int curVal = sumRange(k) - sumRange(k - 1);
    int delta = newVal - curVal;
    k++; // offset for 1-based indexing
    while (k < n) {
      tree[k] += delta;
      k += k & -k;
    }
  }

  public int sumRange(int left, int right) {
    return sumRange(right) - sumRange(left - 1);
  }

  int sumRange(int k) {
    k++; // offset for 1-based indexing
    int totalSum = 0;
    while (k >= 1) {
      totalSum += tree[k];
      k -= k & -k;
    }
    return totalSum;
  }
}

• Useful for range queries where points can be updated.

• O(logn) point update, O(logn) range query.