Collection Kit

FenwickTree

Tree

A FenwickTree, also known as a Binary Indexed Tree, is a data structure that provides efficient methods for cumulative frequency tables, allowing for quick updates and prefix sum queries.

Import Statement

import { FenwickTree } from "collection-kit";

Key Features

Efficient Updates: Supports O(log n) time complexity for updates.
Prefix Sum Queries: Allows for O(log n) time complexity for querying prefix sums.

Common Operations

Update

Modify an element in the array and update the tree.

Query

Retrieve the prefix sum up to a specified index.

Example Code

import { FenwickTree } from "collection-kit";

const arr = [1, 2, 3, 4, 5];
const fenwick = new FenwickTree(arr);

console.log("Prefix sum [0-2]:", fenwick.query(2)); // 6
fenwick.update(1, 5);
console.log("Prefix sum [0-2]:", fenwick.query(2)); // 9