@algorithm.ts/binary-index-tree

中文文档

A typescript implementation of the Binary Index Tree.

The Binary Index Tree is a tree-shaped array structure used to efficiently maintain the prefix sum. There are usually two modes of operation:

1. Single point update, interval query. Modify the value of an element in the number sequence, and solve the prefix sum at a certain position. Solve the sum of any interval $[L, R]$ can be divided into the sum of interval $[1,R]$ and the sum of interval $[1, L-1]$, then perform a subtraction operation.

2. Interval update, single-point query. Add a value to the value of the first $x$ elements in the sequence, and solve the current value of the element at any position in the sequence. Similarly, if you want to add a common value $x$ to any interval $[L, R]$, you can first add $x$ to all elements in [1,R], and then add $-x$ to all elements in [1,L-1].

The above operations are all done under the amortized complexity of $O(\log N)$.

The problem that the Binary Index Tree can solve is a subset of the Segment Tree. Its advantage is that the complexity constant is smaller, and the implementation is simpler and easier to understand.

Install

• npm

  npm install --save @algorithm.ts/binary-index-tree
  

• yarn

  yarn add @algorithm.ts/binary-index-tree
  

Usage

Single-point update And interval query

• Solve numbers:

  import { createBinaryIndexTree1 } from '@algorithm.ts/binary-index-tree'
  
  const MAX_N = 10
  const bit = createBinaryIndexTree1<number>(0)
  bit.init(MAX_N)
  
  // Add 10 on the 2th element.
  bit.add(2, 10)
  
  // Get the prefix sums.
  bit.query(1) // => 0
  bit.query(2) // => 10
  bit.query(/* any integer between [2, 10] */) // => 10
  
  // Add 7 on the 4th element.
  bit.add(4, 7)
  
  // Get the prefix sums.
  bit.query(1) // => 0
  bit.query(2) // => 10
  bit.query(3) // => 10
  bit.query(4) // => 17
  bit.query(/* any integer between [4, 10] */) // => 17
  

• Solve bigint:

  import { createBinaryIndexTree1 } from '@algorithm.ts/binary-index-tree'
  
  const MAX_N = 10
  // Please note that the first parameter is `0n`, which represents the zero
  // element of bigint, and 0 is passed-in in the above example.
  const bit = createBinaryIndexTree1<number>(0n) 
  bit.init(MAX_N)
  
  // Add 10n on the 2th element.
  bit.add(2, 10n)
  
  // Get the prefix sums.
  bit.query(1) // => 0n
  bit.query(2) // => 10n
  bit.query(/* any integer between [2, 10] */) // => 10n
  
  // Add 7n on the 4th element.
  bit.add(4, 7)
  
  // Get the prefix sums.
  bit.query(1) // => 0n
  bit.query(2) // => 10n
  bit.query(3) // => 10n
  bit.query(4) // => 17n
  bit.query(/* any integer between [4, 10] */) // => 17n
  

Interval update and single-point query

• Solve numbers:

  import { createBinaryIndexTree2 } from '@algorithm.ts/binary-index-tree'
  
  const MAX_N = 10
  const bit = createBinaryIndexTree2<number>(0)
  bit.init(MAX_N)
  
  // Add 10 on the first two elements.
  bit.add(2, 10)
  
  // Get the value of x-st element.
  bit.query(1) // => 10
  bit.query(2) // => 10
  bit.query(/* any integer between [3, 10] */) // => 0
  
  // Add 7 on the first four elements.
  bit.add(4, 7)
  
  // Get the value of x-st element.
  bit.query(1) // => 17
  bit.query(2) // => 17
  bit.query(3) // => 17
  bit.query(4) // => 17
  bit.query(/* any integer between [5, 10] */) // => 0
  

• Solve bigint:

  import { createBinaryIndexTree2 } from '@algorithm.ts/binary-index-tree'
  
  const MAX_N = 10
  // Please note that the first parameter is `0n`, which represents the zero
  // element of bigint, and 0 is passed-in in the above example.
  const bit = createBinaryIndexTree2<number>(0n)
  bit.init(MAX_N)
  
  // Add 10 on the first two elements.
  bit.add(2, 10n)
  
  // Get the value of x-st element.
  bit.query(1) // => 10n
  bit.query(2) // => 10n
  bit.query(/* any integer between [3, 10] */) // => 0n
  
  // Add 7 on the first four elements.
  bit.add(4, 7)
  
  // Get the value of x-st element.
  bit.query(1) // => 17n
  bit.query(2) // => 17n
  bit.query(3) // => 17n
  bit.query(4) // => 17n
  bit.query(/* any integer between [5, 10] */) // => 0n
  

• With Mod

  import { createBinaryIndexTree1Mod } from '@algorithm.ts/binary-index-tree'
  
  const MOD = 1e9 + 7
  const bit = createBinaryIndexTree1Mod<number>(0, MOD) 
  
  bit.add(2, <value>)   // <value> should in the range of (-MOD, MOD)
  bit.query(3)
  

  import { createBinaryIndexTree2Mod } from '@algorithm.ts/binary-index-tree'
  
  const MOD = 1e9 + 7
  const bit = createBinaryIndexTree1Mod<bigint>(0, BigInt(MOD)) 
  
  bit.add(2, <value>)   // <value> should in the range of (-MOD, MOD)
  bit.query(3)
  

Related