cp-library
This documentation is automatically generated by online-judge-tools/verification-helper
cp_library/ds/tree/bit/bit5_cls.py
- View this file on GitHub
- Last update: 2025-08-24 20:27:05+09:00
Depends on
- argsort
(cp_library/alg/iter/arg/argsort_fn.py)
- cp_library/alg/iter/sort/isort_parallel_fn.py
- cp_library/bit/pack/packer_cls.py
- cp_library/ds/list/list5_cls.py
- cp_library/ds/tree/bit/bit_base_cls.py
Verified with
Code
import cp_library.__header__
from cp_library.misc.typing import _T
import cp_library.ds.__header__
import cp_library.ds.tree.__header__
import cp_library.ds.tree.bit.__header__
from cp_library.ds.list.list5_cls import list5
from cp_library.ds.tree.bit.bit_base_cls import BITBase
class BIT5(BITBase[_T]):
_lst = list5
K = 5
def _add(bit, i: int, x: _T) -> None: bit._d.add(i, x)
def _op(bit, a, b): return a[0] + b[0], a[1] + b[1], a[2] + b[2], a[3] + b[3], a[4] + b[4]
def _sub(bit, a, b): return a[0] - b[0], a[1] - b[1], a[2] - b[2], a[3] - b[3], a[4] - b[4]'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
https://kobejean.github.io/cp-library
'''
from typing import TypeVar
_S = TypeVar('S'); _T = TypeVar('T'); _U = TypeVar('U'); _T1 = TypeVar('T1'); _T2 = TypeVar('T2'); _T3 = TypeVar('T3'); _T4 = TypeVar('T4'); _T5 = TypeVar('T5'); _T6 = TypeVar('T6')
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ 7 ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┯━┛
┏━━━━━━━━━━━━━━━━━━┓ │
┃ 3 ┃◄────────────────┤
┗━━━━━━━━━━━━━━━━┯━┛ │
┏━━━━━━━━┓ │ ┏━━━━━━━━┓ │
┃ 1 ┃◄──────┤ ┃ 5 ┃◄──────┤
┗━━━━━━┯━┛ │ ┗━━━━━━┯━┛ │
┏━━━┓ │ ┏━━━┓ │ ┏━━━┓ │ ┏━━━┓ │
┃ 0 ┃◄─┤ ┃ 2 ┃◄─┤ ┃ 4 ┃◄─┤ ┃ 6 ┃◄─┤
┗━┯━┛ │ ┗━┯━┛ │ ┗━┯━┛ │ ┗━┯━┛ │
│ │ │ │ │ │ │ │
▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼
┏━━━┓┏━━━┓┏━━━┓┏━━━┓┏━━━┓┏━━━┓┏━━━┓┏━━━┓
┃ 0 ┃┃ 1 ┃┃ 2 ┃┃ 3 ┃┃ 4 ┃┃ 5 ┃┃ 6 ┃┃ 7 ┃
┗━━━┛┗━━━┛┗━━━┛┗━━━┛┗━━━┛┗━━━┛┗━━━┛┗━━━┛
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
Data Structure - Tree - Binary Index Tree
'''
from typing import Generic
def argsort(A: list[int], reverse=False):
P = Packer(len(I := list(A))-1); P.ienumerate(I, reverse); I.sort(); P.iindices(I)
return I
class Packer:
__slots__ = 's', 'm'
def __init__(P, mx: int): P.s = mx.bit_length(); P.m = (1 << P.s) - 1
def enc(P, a: int, b: int): return a << P.s | b
def dec(P, x: int) -> tuple[int, int]: return x >> P.s, x & P.m
def enumerate(P, A, reverse=False): P.ienumerate(A:=list(A), reverse); return A
def ienumerate(P, A, reverse=False):
if reverse:
for i,a in enumerate(A): A[i] = P.enc(-a, i)
else:
for i,a in enumerate(A): A[i] = P.enc(a, i)
def indices(P, A: list[int]): P.iindices(A:=list(A)); return A
def iindices(P, A):
for i,a in enumerate(A): A[i] = P.m&a
def isort_parallel(*L: list, reverse=False):
inv, order = [0]*len(L[0]), argsort(L[0], reverse=reverse)
for i, j in enumerate(order): inv[j] = i
for i, j in enumerate(order):
for A in L: A[i], A[j] = A[j], A[i]
order[inv[i]], inv[j] = j, inv[i]
return L
class list5(Generic[_T1, _T2, _T3, _T4, _T5]):
__slots__ = 'A1', 'A2', 'A3', 'A4', 'A5'
def __init__(lst, A1: list[_T1], A2: list[_T2], A3: list[_T3], A4: list[_T4], A5: list[_T5]):
lst.A1, lst.A2, lst.A3, lst.A4, lst.A5 = A1, A2, A3, A4, A5
def __len__(lst): return len(lst.A1)
def __getitem__(lst, i: int): return lst.A1[i], lst.A2[i], lst.A3[i], lst.A4[i], lst.A5[i]
def __setitem__(lst, i: int, v: tuple[_T1, _T2, _T3, _T4, _T5]): lst.A1[i], lst.A2[i], lst.A3[i], lst.A4[i], lst.A5[i] = v
def __contains__(lst, v: tuple[_T1, _T2, _T3, _T4, _T5]): raise NotImplementedError
def index(lst, v: tuple[_T1, _T2, _T3, _T4, _T5]): raise NotImplementedError
def reverse(lst): lst.A1.reverse(); lst.A2.reverse(); lst.A3.reverse(); lst.A4.reverse(); lst.A5.reverse()
def sort(lst, reverse=False): isort_parallel(lst.A1, lst.A2, lst.A3, lst.A4, lst.A5, reverse=reverse)
def pop(lst): return lst.A1.pop(), lst.A2.pop(), lst.A3.pop(), lst.A4.pop(), lst.A5.pop()
def append(lst, v: tuple[_T1, _T2, _T3, _T4, _T5]):
v1, v2, v3, v4, v5 = v
lst.A1.append(v1); lst.A2.append(v2); lst.A3.append(v3); lst.A4.append(v4); lst.A5.append(v5)
def add(lst, i: int, v: tuple[_T1, _T2, _T3, _T4, _T5]): lst.A1[i] += v[0]; lst.A2[i] += v[1]; lst.A3[i] += v[2]; lst.A4[i] += v[3]; lst.A5[i] += v[4]
from typing import Generic, Union, Callable, Optional
class BITBase(Generic[_T]):
_lst = list
K: int = 1
def __init__(bit, v: Union[int, list[_T]], e: _T = None) -> None:
if isinstance(v, int):
bit._n = v
if bit._lst is list:
bit._d = [e]*v if e is not None else [0]*v
elif e is not None:
bit._d = bit._lst(*([e_]*v for e_ in e))
else:
bit._d = bit._lst(*([0]*v for _ in range(bit.K)))
else:
bit.build(v)
bit.e = e if e is not None else (0 if bit._lst is list else tuple(0 for _ in range(bit.K)))
bit._lb = 1 << bit._n.bit_length()
def build(bit, data: list[_T]):
bit._n = len(data)
if bit._lst is list:
bit._d = bit._lst(data)
else:
bit._d = bit._lst(*([data[i][j] for i in range(len(data))] for j in range(len(data[0]))))
for i in range(bit._n):
if (r := i | i + 1) < bit._n:
bit._add(r, bit._d[i])
def _add(bit, i: int, x: _T) -> None:
bit._d[i] = bit._op(bit._d[i], x)
def _op(bit, a: _T, b: _T) -> _T:
return a + b
def _sub(bit, a: _T, b: _T) -> _T:
return a - b
def add(bit, i: int, x: _T) -> None:
while i < bit._n: bit._add(i, x); i |= i + 1
def sum(bit, n: int) -> _T:
s = bit.e
while n: s, n = bit._op(s, bit._d[n - 1]), n & n - 1
return s
def sum_range(bit, l: int, r: int) -> _T:
s = bit.e
while r: s, r = bit._op(s, bit._d[r - 1]), r & r - 1
while l: s, l = bit._sub(s, bit._d[l - 1]), l & l - 1
return s
def __len__(bit) -> int: return bit._n
def __getitem__(bit, i: int) -> _T:
s, l = bit._d[i], i & (i + 1)
while l != i: s, i = bit._sub(s, bit._d[i - 1]), i - (i & -i)
return s
get = __getitem__
def __setitem__(bit, i: int, x: _T) -> None:
bit.add(i, bit._sub(x, bit[i]))
set = __setitem__
def prelist(bit) -> list[_T]:
pre = [bit.e] + bit._d[:] if bit._lst is list else bit._lst(*([e_] * (bit._n + 1) for e_ in bit.e))
for i in range(bit._n): pre[i+1] = bit._d[i]
for i in range(bit._n + 1):
if i & i - 1 < bit._n + 1:
pre[i] = bit._op(pre[i], pre[i & i - 1])
return pre
def bisect_left(bit, v, key: Optional[Callable] = None) -> int:
i = 0
s = bit.e
if v <= s: return -1
m = bit._lb
if key:
while m := m >> 1:
if (ni := m | i) <= bit._n and key(ns := bit._op(s, bit._d[ni - 1])) < v:
s, i = ns, ni
else:
while m := m >> 1:
if (ni := m | i) <= bit._n and (ns := bit._op(s, bit._d[ni - 1])) < v:
s, i = ns, ni
return i
def bisect_right(bit, v, key: Optional[Callable] = None) -> int:
i = 0
s = bit.e
m = bit._lb
if key:
while m := m >> 1:
if (ni := m | i) <= bit._n and key(ns := bit._op(s, bit._d[ni - 1])) <= v:
s, i = ns, ni
else:
while m := m >> 1:
if (ni := m | i) <= bit._n and (ns := bit._op(s, bit._d[ni - 1])) <= v:
s, i = ns, ni
return i
class BIT5(BITBase[_T]):
_lst = list5
K = 5
def _add(bit, i: int, x: _T) -> None: bit._d.add(i, x)
def _op(bit, a, b): return a[0] + b[0], a[1] + b[1], a[2] + b[2], a[3] + b[3], a[4] + b[4]
def _sub(bit, a, b): return a[0] - b[0], a[1] - b[1], a[2] - b[2], a[3] - b[3], a[4] - b[4]