FenwickTree Implementation For Range Sum Leetcode

FenwickTree.js

class FenwickTree {
  constructor(size) {
    this.size = size;
    this.tree = Array(size + 1).fill(0); // Fenwick Tree array with 1-based indexing
  }

  update(index, delta) {
    // Update the tree with the delta
    for (let i = index; i <= this.size; i += i & -i) {
      this.tree[i] += delta; // Add delta to the current value
    }
  }

  query(index) {
    // Query the prefix sum up to the given index
    let sum = 0;
    for (let i = index; i > 0; i -= i & -i) {
      sum += this.tree[i];
    }
    return sum;
  }
}

class NumArray {
  constructor(nums) {
    this.nums = nums;
    this.size = nums.length;
    this.fenwickTree = new FenwickTree(this.size);

    // Build the Fenwick Tree with the initial values
    for (let i = 0; i < this.size; i++) {
      this.fenwickTree.update(i + 1, nums[i]); // 1-based index
    }
  }

  update(index, val) {
    const delta = val - this.nums[index];
    this.nums[index] = val;
    this.fenwickTree.update(index + 1, delta); // 1-based index
  }

  sumRange(left, right) {
    return this.fenwickTree.query(right + 1) - this.fenwickTree.query(left); // 1-based index
  }
}

// Example usage:
const nums = [1, 3, 5];
const numArray = new NumArray(nums);

console.log(numArray.sumRange(0, 2)); // Output: 9

numArray.update(1, 2); // Update index 1 to value 2
console.log(numArray.sumRange(0, 2)); // Output: 8