@yiminghe/binary-indexed-tree v0.2.0

api

declare class IntegralArray {
    /**
     * Get a value from the array with O(1) complexity
     * @param index - The index of the value to get
     * @returns - The value with the given index
     */
    get(index: number): number;
    /**
     * Accumulate the first n numbers in the array with O(log(n)) complexity
     * @param count - The number of values to sum up from the head of the array
     * @returns - The sum of the values
     */
    accumulate(count: number): number;
    /**
     * Update a value in the array by delta with O(1) complexity
     * @param index - The index of the value in array
     * @param delta - The delta to be applied to the value
     * @returns - The updated value
     */
    update(index: number, delta: number): number;
    /**
     * Update a value in the array with O(1) complexity
     * @param index - The index of the value to set
     * @param value - The new value
     * @returns - The updated value
     */
    set(index: number, value: number): number;
    /**
     * Insert a set of slots filled with the default value with O(k*log(n)) complexity
     * where k is the number of values in the array changed from default
     * @param index - The position to insert new slots
     * @param count - The number of slots to be inserted
     */
    insert(index: number, count: number): void;
    /**
     * Delete a segment of values from the array with O(k*log(n)) complexity
     * where k is the number of values in the array changed from default
     * @param index - The position of the first value to delete
     * @param count - The number of values to delete
     */
    delete(index: number, count: number): void;
}

class AccumulativeArray extends IntegralArray {
    /**
     * A non-negative numeric array with the ability to sum up a segment of members with
     * O(log(n)) complexity, and to locate a position close to a given accumulation also
     * with O(log(n)) complexity.
     * @param defaultValue - The default value the array is filled with
     */
    constructor(defaultValue?: number);
    /**
     * Update a value in the array by delta with O(1) complexity
     * @override
     * @param index - The index of the value in array
     * @param delta - The delta to be applied to the value
     * @returns - The updated value
     */
    update(index: number, delta: number): number;
    /**
     * Update a value in the array with O(1) complexity
     * @override
     * @param index - The index of the value to set
     * @param value - The new value
     * @returns - The updated value
     */
    set(index: number, value: number): number;
    /**
     * Find the minimum i so that accumulate(i) >= acc, return 0 if acc <= 0 (the lower bound rule)
     * @param acc - The accumulation to be locate from the array
     * @returns - The index located according to the lower bound rule
     */
    lowerBound(acc: number): number;
    /**
     * Find the maximum i so that accumulate(i) <= acc, return -1 if acc < 0 (the upper bound rule)
     * @param acc - The accumulation to be locate from the array
     * @returns - The index located according to the upper bound rule
     */
    upperBound(acc: number): number;
}
export default AccumulativeArray;

refer

• https://en.wikipedia.org/wiki/Fenwick_tree
• https://www.topcoder.com/community/competitive-programming/tutorials/binary-indexed-trees/
• https://lotabout.me/2018/binary-indexed-tree/