Skip to content

Instantly share code, notes, and snippets.

@anish000kumar
Created June 4, 2021 05:39
Show Gist options
  • Save anish000kumar/080215182788c2b85abf8718a557368f to your computer and use it in GitHub Desktop.
Save anish000kumar/080215182788c2b85abf8718a557368f to your computer and use it in GitHub Desktop.
FenwickTree Javascript implementation
class FenwickTree{
constructor(array){
this.source = [...array]
this.length = this.source.length;
this.fenwick = new Array(array.length+1).fill(0)
this.build();
}
build(){
for(let i = 0; i < this.length; i++)
this.updateByDiff(i, this.source[i])
}
update(index, value){
const diff = value - this.source[index];
this.source[index] = value;
this.updateByDiff(index, diff)
}
updateByDiff(index, diff){
index += 1
while(index < this.length){
this.fenwick[index] += diff
index += index & -index
}
}
getSum(index){
index += 1
let ans = 0
while(index > 0){
ans += this.fenwick[index]
index -= index & -index
}
return ans
}
getRangeSum(fromIndex, toIndex){
return this.getSum(toIndex) - this.getSum(fromIndex-1)
}
}
// example
const source = [1, 2, 3, 4, 5, 6, 9]
const bit = new FenwickTree(source);
console.log(bit.getRangeSum(2, 3))
bit.update(3, 9)
console.log(bit.getRangeSum(2, 3))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment