Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumsegment-tree-bit

Range Sum Query - Mutable

Problem (restated)

An integer array that supports update(index, val) (point assignment) and sumRange(left, right) (inclusive range sum). Both should be fast under a mix of updates and queries.

Intuition

A prefix array makes sumRange O(1) but update O(n). A Fenwick tree (BIT) stores partial sums at i covering lowbit(i) elements, so both update and prefix query walk O(log n) ancestors. Range sum is prefix(r) - prefix(l-1). Keep a copy of the array so assignment becomes a delta.

Approaches

Fenwick tree (BIT)

Unverified

Time O(log n) update / querySpace O(n)

Idea. 1-indexed internally: i += 1, then i += i & -i on update and i -= i & -i on prefix. Constructor inserts every nums[i] as a delta. update applies val - arr[i].

Walkthrough. [1,3,5], sumRange(0,2)=9. update(1,2) deltas -1. sumRange(0,2)=8.

Trade-offs. BIT is the template for invertible range sums. A segment tree also works and extends to min/max. Do not 0-index the tree array; lowbit needs the extra slot at 0 unused.

Solution

class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
  rangeSum(l: number, r: number): number {
    return this.prefixSum(r) - (l > 0 ? this.prefixSum(l - 1) : 0);
  }
}

export class NumArray {
  private arr: number[];
  private bit: BIT;
  constructor(nums: number[]) {
    this.arr = nums.slice();
    this.bit = new BIT(nums.length);
    for (let i = 0; i < nums.length; i++) this.bit.update(i, nums[i]!);
  }
  update(index: number, val: number): void {
    this.bit.update(index, val - this.arr[index]!);
    this.arr[index] = val;
  }
  sumRange(left: number, right: number): number {
    return this.bit.rangeSum(left, right);
  }
}

class BIT {
  private n: number;
  private tree: number[];
  constructor(n: number) {
    this.n = n;
    this.tree = new Array<number>(n + 1).fill(0);
  }
  update(i: number, delta: number): void {
    for (i++; i <= this.n; i += i & -i) this.tree[i]! += delta;
  }
  prefixSum(i: number): number {
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.tree[i]!;
    return s;
  }
  rangeSum(l: number, r: number): number {
    return this.prefixSum(r) - (l > 0 ? this.prefixSum(l - 1) : 0);
  }
}

export class NumArray {
  private arr: number[];
  private bit: BIT;
  constructor(nums: number[]) {
    this.arr = nums.slice();
    this.bit = new BIT(nums.length);
    for (let i = 0; i < nums.length; i++) this.bit.update(i, nums[i]!);
  }
  update(index: number, val: number): void {
    this.bit.update(index, val - this.arr[index]!);
    this.arr[index] = val;
  }
  sumRange(left: number, right: number): number {
    return this.bit.rangeSum(left, right);
  }
}

Template connection

BIT point-update / range-sum. LC 303 is the immutable prefix-sum cousin; LC 308 is this in 2D.

Reflection

The Fenwick tree is 1-indexed. An update adds a delta. A range is the difference of two prefixes. Both are O(log n).
The constructor writes the initial array into the leaves. A left bound of 0 is a prefix of 0.
A negative delta is legal. A plain array would rescan the range on every query.