1.0.4 • Published 2 years ago
fenwicktreesol v1.0.4
Description
Fenwick Tree in Solidity with log(n) update and query to calculate prefix sums.
Supported by TypeScript package feenwicktreejs.
Usage
The underlying array should be computed off-chain to save gas.
import * as fenwicktreejs from "fenwicktreejs";
const fenwickTree = new fenwicktreejs.FenwickTree([1, 5, 2, 0, 5]);
console.log(fenwickTree.fenwick); // [ 0, 1, 6, 2, 8, 5 ]
Use the underlying array on-chain when intializing the Fenwick tree.
pragma solidity >=0.7.0 <0.9.0;
import "fenwicktreesol/contracts/FenwickTree.sol";
import "hardhat/console.sol";
contract FenwickTreeConsumer {
function logPrefixSum() public {
// Create Fenwick tree for [1, 5, 2, 0, 5]
uint256[] memory fenwicktreeArray = new uint256[](6);
fenwicktreeArray[0] = 0;
fenwicktreeArray[1] = 1;
fenwicktreeArray[2] = 6;
fenwicktreeArray[3] = 2;
fenwicktreeArray[4] = 8;
fenwicktreeArray[5] = 5;
FenwickTree fenwicktree = new FenwickTree(fenwicktreeArray);
// Print prefix sum for [1, 5, 2, 0, 5]
console.log(fenwicktree.query(1)); // 1
console.log(fenwicktree.query(2)); // 6
console.log(fenwicktree.query(3)); // 8
console.log(fenwicktree.query(4)); // 8
console.log(fenwicktree.query(5)); // 13
// Update Fenwick tree to [10, 5, 2, 0, 5]
fenwicktree.update(1, 9);
// Print prefix sum for [10, 5, 2, 0, 5]
console.log(fenwicktree.query(1)); // 10
console.log(fenwicktree.query(2)); // 15
console.log(fenwicktree.query(3)); // 17
console.log(fenwicktree.query(4)); // 17
console.log(fenwicktree.query(5)); // 22
}
}
Note
- query(i) is 1-indexed
- update(i, diff) is 1-indexed
- updateSub(i, diff) is 1-indexed