Fenwick Tree Tutorial
Introduction
A Fenwick Tree, also known as a Binary Indexed Tree (BIT), is a data structure that provides efficient methods for querying and updating prefix sums in an array. It supports operations like point updates and prefix sum queries in O(log n) time.
Key Operations
- Update: Increment the value at a specific index.
- Query: Get the sum of values from the start of the array to a specific index.
Fenwick Tree Structure
The Fenwick Tree is typically represented as an array where each position maintains a cumulative sum of elements.
Implementation
Here’s a basic implementation of a Fenwick Tree in JavaScript:
class FenwickTree {
constructor(size) {
this.size = size;
this.tree = new Array(size + 1).fill(0);
}
// Increment the value at index i by delta
update(index, delta) {
while (index <= this.size) {
this.tree[index] += delta;
index += index & -index; // Move to the next index
}
}
// Get the prefix sum from the start to index i
query(index) {
let sum = 0;
while (index > 0) {
sum += this.tree[index];
index -= index & -index; // Move to the parent index
}
return sum;
}
// Query the sum from index i to j (inclusive)
rangeQuery(i, j) {
return this.query(j) - this.query(i - 1);
}
}
// Example Usage
const fenwick = new FenwickTree(10);
// Incrementing values
fenwick.update(1, 5);
fenwick.update(3, 3);
fenwick.update(5, 7);
// Querying prefix sums
console.log(fenwick.query(5)); // Output: 15 (5 + 3 + 7)
Implementation with an Array
class FenwickTree {
constructor(arr) {
this.size = arr.length;
this.tree = new Array(this.size + 1).fill(0); // Fenwick Tree is 1-indexed
// Build the tree by updating for each element in the array
for (let i = 0; i < arr.length; i++) {
this.update(i + 1, arr[i]); // Convert to 1-indexed
}
}
// Increment the value at index i by delta
update(index, delta) {
while (index <= this.size) {
this.tree[index] += delta;
index += index & -index; // Move to the next index
}
}
// Get the prefix sum from the start to index i
query(index) {
let sum = 0;
while (index > 0) {
sum += this.tree[index];
index -= index & -index; // Move to the parent index
}
return sum;
}
// Query the sum from index i to j (inclusive)
rangeQuery(i, j) {
return this.query(j) - this.query(i - 1);
}
}
// Example Usage
const arr = [5, 3, 7, 9, 6]; // Your initial array
const fenwick = new FenwickTree(arr);
// Checking the internal tree array
console.log(fenwick.tree); // Output: internal Fenwick Tree structure
// Querying prefix sums or range sums
console.log(fenwick.query(3)); // Output: Sum from index 1 to 3 (5 + 3 + 7 = 15)
console.log(fenwick.rangeQuery(2, 4)); // Output: Sum from index 2 to 4 (3 + 7 + 9 = 19)
2D Binary Indexed Tree Solution
class NumMatrix {
constructor(matrix) {
this.m = matrix.length;
this.n = matrix[0].length;
this.tree = Array.from({ length: this.m + 1 }, () => Array(this.n + 1).fill(0));
this.matrix = Array.from({ length: this.m }, () => Array(this.n).fill(0));
// Build the BIT
for (let i = 0; i < this.m; i++) {
for (let j = 0; j < this.n; j++) {
this.update(i, j, matrix[i][j]);
}
}
}
// Update BIT with delta
update(x, y, delta) {
const diff = delta - this.matrix[x][y];
this.matrix[x][y] = delta;
for (let i = x + 1; i <= this.m; i += i & -i) {
for (let j = y + 1; j <= this.n; j += j & -j) {
this.tree[i][j] += diff;
}
}
}
// Query sum from (1,1) to (x,y)
query(x, y) {
let sum = 0;
for (let i = x + 1; i > 0; i -= i & -i) {
for (let j = y + 1; j > 0; j -= j & -j) {
sum += this.tree[i][j];
}
}
return sum;
}
// Calculate sum for the submatrix
sumRegion(row1, col1, row2, col2) {
return this.query(row2, col2)
- (row1 > 0 ? this.query(row1 - 1, col2) : 0)
- (col1 > 0 ? this.query(row2, col1 - 1) : 0)
+ (row1 > 0 && col1 > 0 ? this.query(row1 - 1, col1 - 1) : 0);
}
}
// Example usage:
const matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
];
const numMatrix = new NumMatrix(matrix);
console.log(numMatrix.sumRegion(2, 1, 4, 3)); // Output: 8
numMatrix.update(3, 2, 2);
console.log(numMatrix.sumRegion(2, 1, 4, 3)); // Output: 10