import type { BinaryIndexTree } from './types' ; import { lowbit } from './util' ; param ZERO param MOD returns export function createBinaryIndexTree2Mod < T extends number | bigint > ( ZERO , MOD ) { let _size = 0 ; const _nodes = [ ZERO ] ; return { init , add , query } ; param N function init ( N ) { _size = N ; if ( _nodes . length <= _size ) _nodes . length = _size + 1 ; _nodes . fill ( ZERO , 1 , _size + 1 ) ; } param xth param value function add ( xth , value ) { if ( value < 0 ) value += MOD as any ; for ( let i = xth ; i > 0 ; i -= lowbit ( i ) ) { _nodes [ i ] = modAdd ( _nodes [ i ] , value ) ; } } param xth function query ( xth ) { if ( xth < 1 ) return ZERO ; let result = ZERO ; for ( let i = xth ; i <= _size ; i += lowbit ( i ) ) { result = modAdd ( result , _nodes [ i ] ) ; } return result ; } param x param y returns function modAdd ( x , y ) { const result = ( x as any ) + ( y as any ) ; return result >= MOD ? result - MOD : result ; } }