307. Range Sum Query - Mutable

• 307. Range Sum Query - Mutable
  • Description
  • Solution

Description

Here

Solution

没啥好说，BIT经典

private void updateByDiff(int i, int diff) {
  // 这个技巧可以使得代码简单很多
  // tree[] should have one empty slot.
  ++i;
  while (i <= n) {
    tree[i] += diff;
    i += (i & (-i));
  }
}

private int getPreSum(int i) {
  ++i;
  int sum = 0;
  while (i > 0) {
    sum += tree[i];
    i -= (i & -i);
  }

  return sum;
}