Using Fenwick Tree Patterns
1. Implementing Point Update Range Query
A Fenwick Tree (also known as a Binary Indexed Tree) is a data structure that efficiently supports two operations:
- Point updates: updating the value at a specific index
- Range queries: computing the sum of elements in a range [1, i] or [l, r]
This implementation focuses on point updates and prefix sum range queries.
Example: Basic Fenwick Tree Implementation
class FenwickTree {
constructor(size) {
this.size = size;
this.tree = new Array(size + 1).fill(0);
}
// Update the value at index i (1-based)
update(i, delta) {
while (i <= this.size) {
this.tree[i] += delta;
i += i & (-i);
}
}
// Get prefix sum from index 1 to i (1-based)
query(i) {
let sum = 0;
while (i > 0) {
sum += this.tree[i];
i -= i & (-i);
}
return sum;
}
// Get range sum from l to r (1-based)
rangeQuery(l, r) {
return this.query(r) - this.query(l - 1);
}
}
// Example usage:
const ft = new FenwickTree(5);
ft.update(1, 3); // Add 3 to index 1
ft.update(2, 5); // Add 5 to index 2
console.log(ft.query(2)); // Output: 8 (3 + 5)
console.log(ft.rangeQuery(1, 2)); // Output: 8| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| update(i, delta) | Updates the value at index i by adding delta | O(log n) | O(n) |
| query(i) | Returns prefix sum from index 1 to i | O(log n) | O(1) |
| rangeQuery(l, r) | Returns sum from index l to r | O(log n) | O(1) |
Note: Indexing is 1-based in this implementation. The tree array has size n+1 to simplify indexing.
Key Points
- Fenwick Tree allows efficient point updates and prefix sum queries.
- Each operation runs in O(log n) time.
- It uses a binary representation trick to navigate the tree structure.
2. Implementing Range Update Point Query
A Fenwick Tree (also known as a Binary Indexed Tree) can be adapted to support range updates and point queries. This is useful when you need to efficiently update a range of elements and then query the value at a specific index.
The key idea is to maintain two Fenwick Trees:
BIT1: For handling range updates.BIT2: For handling point queries.
Below is the implementation:
Example: Implementing Range Update Point Query
class FenwickTreeRangeUpdate {
constructor(size) {
this.size = size;
this.bit1 = new Array(size + 1).fill(0);
this.bit2 = new Array(size + 1).fill(0);
}
// Helper function to update BIT
updateBIT(bit, index, delta) {
while (index <= this.size) {
bit[index] += delta;
index += index & (-index);
}
}
// Helper function to get prefix sum from BIT
getPrefixSum(bit, index) {
let sum = 0;
while (index > 0) {
sum += bit[index];
index -= index & (-index);
}
return sum;
}
// Range update: add value to all elements from index left to right
rangeUpdate(left, right, value) {
this.updateBIT(this.bit1, left, value);
this.updateBIT(this.bit1, right + 1, -value);
this.updateBIT(this.bit2, left, value * (left - 1));
this.updateBIT(this.bit2, right + 1, -value * right);
}
// Point query: get value at index
pointQuery(index) {
return this.getPrefixSum(this.bit1, index) * index - this.getPrefixSum(this.bit2, index);
}
}
// Example usage:
const ft = new FenwickTreeRangeUpdate(10);
ft.rangeUpdate(2, 5, 3); // Add 3 to indices 2 through 5
console.log(ft.pointQuery(3)); // Output: 3
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| rangeUpdate(left, right, value) | Updates all elements in range [left, right] by adding value |
O(log n) | O(1) |
| pointQuery(index) | Returns the value at index |
O(log n) | O(1) |
Note: The implementation uses two BITs to support range updates efficiently. This allows for both point queries and range updates in logarithmic time.
3. Implementing Range Update Range Query
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Range Update | Updates all elements in a range [l, r] by adding a value | O(log n) | O(n) |
| Range Query | Computes sum of elements in a range [l, r] | O(log n) | O(n) |
Example: Range Update and Query
class FenwickTree {
constructor(size) {
this.size = size;
this.tree = new Array(size + 1).fill(0);
}
updateRange(l, r, delta) {
this.update(l, delta);
this.update(r + 1, -delta);
}
update(index, delta) {
for (let i = index; i <= this.size; i += i & -i) {
this.tree[i] += delta;
}
}
query(index) {
let sum = 0;
for (let i = index; i > 0; i -= i & -i) {
sum += this.tree[i];
}
return sum;
}
rangeQuery(l, r) {
return this.query(r) - this.query(l - 1);
}
}
// Usage example
const ft = new FenwickTree(5);
ft.updateRange(1, 3, 2); // Add 2 to indices 1-3
console.log(ft.rangeQuery(2, 4)); // Sum from index 2 to 4
Note: The Fenwick Tree supports efficient range updates and queries using two separate trees or by maintaining difference arrays.
4. Solving Inversion Count
An inversion in an array is a pair of indices (i, j) such that i < j and arr[i] > arr[j]. Fenwick Trees (Binary Indexed Trees) can efficiently count inversions in O(n log n) time.
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Count Inversions | Using Fenwick Tree to count inversions in an array | O(n log n) | O(n) |
Example: Counting Inversions Using Fenwick Tree
function countInversions(arr) {
const n = arr.length;
const BIT = new Array(n + 1).fill(0);
// Coordinate compression
const sorted = [...arr].sort((a, b) => a - b);
const coordMap = new Map();
sorted.forEach((val, i) => coordMap.set(val, i + 1));
let invCount = 0;
// Traverse from right to left
for (let i = n - 1; i >= 0; i--) {
const compressed = coordMap.get(arr[i]);
// Query how many elements smaller than current are already processed
for (let j = compressed - 1; j > 0; j -= j & (-j)) {
invCount += BIT[j];
}
// Update BIT with current element
for (let j = compressed; j <= n; j += j & (-j)) {
BIT[j]++;
}
}
return invCount;
}
// Example usage
const arr = [8, 4, 2, 1];
console.log(countInversions(arr)); // Output: 6
Note: Coordinate compression is used to handle large values efficiently.
Key Points
- Fenwick Tree allows efficient prefix sum queries and updates.
- Coordinate compression is essential for large value ranges.
- Time complexity is O(n log n) due to coordinate compression and BIT operations.
5. Finding Count of Smaller Elements
Use a Fenwick Tree (Binary Indexed Tree) to efficiently count how many elements are smaller than a given value in a dynamic array.
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| query | Get count of elements less than a value | O(log n) | O(n) |
| update | Add or modify an element in the array | O(log n) | O(n) |
Example: Count Smaller Elements
class FenwickTree {
constructor(size) {
this.size = size;
this.tree = new Array(size + 1).fill(0);
}
update(index, delta) {
for (let i = index; i <= this.size; i += i & -i) {
this.tree[i] += delta;
}
}
query(index) {
let sum = 0;
for (let i = index; i > 0; i -= i & -i) {
sum += this.tree[i];
}
return sum;
}
}
// Example usage
const arr = [5, 2, 6, 1];
const ft = new FenwickTree(1000);
let result = [];
for (let i = arr.length - 1; i >= 0; i--) {
result[i] = ft.query(arr[i] - 1);
ft.update(arr[i], 1);
}
console.log(result); // [2, 1, 1, 0]
Note: The Fenwick Tree is updated from right to left to ensure that when querying for elements smaller than a value, only already processed elements are counted.
6. Implementing 2D Point Update
A Fenwick Tree (Binary Indexed Tree) can be extended to two dimensions to support efficient point updates and range queries. This implementation handles 2D point updates where each update modifies a single cell in the grid.
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Update Point | Updates the value at a specific (x, y) coordinate in the 2D grid | O(log² n) | O(n²) |
| Query Range | Computes prefix sum up to (x, y) coordinate | O(log² n) | - |
Example: 2D Fenwick Tree Point Update
class FenwickTree2D {
constructor(rows, cols) {
this.rows = rows;
this.cols = cols;
this.tree = Array(rows + 1).fill().map(() => Array(cols + 1).fill(0));
}
update(x, y, delta) {
for (let i = x; i <= this.rows; i += i & -i) {
for (let j = y; j <= this.cols; j += j & -j) {
this.tree[i][j] += delta;
}
}
}
query(x, y) {
let sum = 0;
for (let i = x; i > 0; i -= i & -i) {
for (let j = y; j > 0; j -= j & -j) {
sum += this.tree[i][j];
}
}
return sum;
}
}
// Example usage:
const ft = new FenwickTree2D(4, 4);
ft.update(2, 2, 5); // Add 5 to cell (2, 2)
console.log(ft.query(3, 3)); // Sum up to (3, 3)7. Implementing 2D Range Query
A Fenwick Tree (Binary Indexed Tree) can be extended to support 2D range queries. This is useful for problems involving 2D grids where you need to perform updates and range sum queries efficiently.
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| 2D Fenwick Tree | Supports updates and range sum queries in 2D grid | O(log²n) | O(n²) |
Example: 2D Fenwick Tree Implementation
class FenwickTree2D {
constructor(rows, cols) {
this.rows = rows;
this.cols = cols;
this.tree = Array(rows + 1).fill().map(() => Array(cols + 1).fill(0));
}
update(row, col, delta) {
for (let i = row; i <= this.rows; i += i & -i) {
for (let j = col; j <= this.cols; j += j & -j) {
this.tree[i][j] += delta;
}
}
}
query(row, col) {
let sum = 0;
for (let i = row; i > 0; i -= i & -i) {
for (let j = col; j > 0; j -= j & -j) {
sum += this.tree[i][j];
}
}
return sum;
}
rangeQuery(row1, col1, row2, col2) {
return this.query(row2, col2) - this.query(row1 - 1, col2) -
this.query(row2, col1 - 1) + this.query(row1 - 1, col1 - 1);
}
}
// Example usage:
const ft = new FenwickTree2D(3, 3);
ft.update(1, 1, 5); // Add 5 to position (1,1)
console.log(ft.rangeQuery(1, 1, 2, 2)); // Sum from (1,1) to (2,2)
Note: The 2D Fenwick Tree uses two nested loops to update and query elements, resulting in O(log²n) time complexity for each operation.
8. Solving Order Statistics
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Find k-th smallest element | Retrieve the k-th smallest element in a dynamic array | O(log n) | O(n) |
| Count elements <= x | Count how many elements are less than or equal to a value x | O(log n) | O(n) |
| Insert element | Add a new element to the structure | O(log n) | O(n) |
| Delete element | Remove an existing element from the structure | O(log n) | O(n) |
Example: Finding k-th smallest element
class FenwickTree {
constructor(size) {
this.size = size;
this.tree = new Array(size + 1).fill(0);
}
update(index, delta) {
for (let i = index; i <= this.size; i += i & -i) {
this.tree[i] += delta;
}
}
query(index) {
let sum = 0;
for (let i = index; i > 0; i -= i & -i) {
sum += this.tree[i];
}
return sum;
}
kthSmallest(k) {
let left = 1, right = this.size;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (this.query(mid) < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
// Usage example:
const ft = new FenwickTree(1000);
ft.update(5, 1); // Insert element 5
ft.update(3, 1); // Insert element 3
console.log(ft.kthSmallest(1)); // Output: 3 (first smallest)
console.log(ft.kthSmallest(2)); // Output: 5 (second smallest)
Note: The Fenwick Tree is particularly efficient for solving order statistics problems because it supports both updates and prefix queries in O(log n) time.
9. Finding Longest Increasing Subsequence
The Longest Increasing Subsequence (LIS) problem involves finding the length of the longest subsequence in an array where elements are in strictly increasing order.
This problem can be solved efficiently using a Fenwick Tree (Binary Indexed Tree) for optimization, particularly when dealing with large datasets or frequent updates.
| Approach | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Naive Dynamic Programming | Use a DP array where dp[i] represents the length of LIS ending at index i. |
O(n^2) |
O(n) |
| Fenwick Tree Optimization | Use Fenwick Tree to maintain maximum LIS length up to a certain value. | O(n log n) |
O(n) |
Example: Using Fenwick Tree for LIS
class FenwickTree {
constructor(size) {
this.size = size;
this.tree = new Array(size + 1).fill(0);
}
update(index, delta) {
for (let i = index; i <= this.size; i += i & -i) {
this.tree[i] = Math.max(this.tree[i], delta);
}
}
query(index) {
let maxVal = 0;
for (let i = index; i > 0; i -= i & -i) {
maxVal = Math.max(maxVal, this.tree[i]);
}
return maxVal;
}
}
function lengthOfLIS(nums) {
const n = nums.length;
if (n === 0) return 0;
// Coordinate compression
const sorted = [...new Set(nums)].sort((a, b) => a - b);
const map = new Map();
sorted.forEach((val, i) => map.set(val, i + 1));
const ft = new FenwickTree(sorted.length);
let maxLength = 0;
for (let i = 0; i < n; i++) {
const compressedIndex = map.get(nums[i]);
const prevMax = ft.query(compressedIndex - 1);
const currentLength = prevMax + 1;
ft.update(compressedIndex, currentLength);
maxLength = Math.max(maxLength, currentLength);
}
return maxLength;
}
// Example usage:
const nums = [10, 9, 2, 5, 3, 7, 101, 18];
console.log(lengthOfLIS(nums)); // Output: 4 (subsequence: [2, 3, 7, 18])
Note: Coordinate compression is essential to reduce the range of values for Fenwick Tree, allowing efficient updates and queries.
10. Optimizing Space Complexity
| Operation | Space Complexity | Notes |
|---|---|---|
| Fenwick Tree Construction | O(n) |
Building tree from initial array |
| Query Operation | O(log n) |
Range sum query or point update |
| Update Operation | O(log n) |
Point update or range update |
Example: Space-Optimized Fenwick Tree Implementation
class FenwickTree {
constructor(size) {
this.size = size;
this.tree = new Array(size + 1).fill(0);
}
update(index, delta) {
for (let i = index; i <= this.size; i += i & -i) {
this.tree[i] += delta;
}
}
query(index) {
let sum = 0;
for (let i = index; i > 0; i -= i & -i) {
sum += this.tree[i];
}
return sum;
}
rangeQuery(l, r) {
return this.query(r) - this.query(l - 1);
}
}
// Usage
const ft = new FenwickTree(10);
ft.update(1, 5); // Add 5 to index 1
console.log(ft.query(1)); // Output: 5