阅读中文版本

Fenwick Tree CLI

A Node CLI that builds a Fenwick tree (binary indexed tree) from an array and answers prefix-sum queries with point updates in O(log n).

node --version

node fenwick.mjs 1,2,3,4,5 query 3 update 2 10 query 3

node --test fenwick.test.mjs

Prints the prefix sum for each query command, reflecting point updates applied along the way.

What it does

Builds a Fenwick tree (binary indexed tree) from the input array, then processes query and update commands. A query prints the prefix sum up to an index; an update adds a delta to a position. Both operations are O(log n) using the least-significant-bit trick to walk the tree.

const nums = process.argv[2].split(',').map(Number);
const n = nums.length;
const tree = new Array(n + 1).fill(0);
const update = (i, delta) => { for (i++; i <= n; i += i & -i) tree[i] += delta; };
const query = i => { let s = 0; for (i++; i > 0; i -= i & -i) s += tree[i]; return s; };
nums.forEach((v, i) => update(i, v));
const cmds = process.argv.slice(3);
for (let i = 0; i < cmds.length; i += 2) {
  if (cmds[i] === 'query') console.log('prefix sum ' + cmds[i+1] + ' = ' + query(+cmds[i+1]));
  else if (cmds[i] === 'update') update(+cmds[i+1], +cmds[i+2++]);
}

Run and verify

node fenwick.mjs 1,2,3,4,5 query 3 update 2 10 query 3

Run the test command to check the implementation: node --test fenwick.test.mjs.

Expected Output

For the array 1,2,3,4,5: prefix sum up to index 3 is 1+2+3+4=10, after adding 10 to index 2 the prefix sum up to index 3 is 1+2+13+4=20:

prefix sum 3 = 10
prefix sum 3 = 20

Limitations

The tree supports point updates and prefix-sum queries only; range sums require two prefix queries. Negative deltas are allowed for decrements.