cp-library
This documentation is automatically generated by online-judge-tools/verification-helper
test/unittests/ds/tree/bit/bit3_cls_test.py
- View this file on GitHub
- Last update: 2025-08-24 20:27:05+09:00
- Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
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/list3_cls.py
- cp_library/ds/tree/bit/bit3_cls.py
- cp_library/ds/tree/bit/bit_base_cls.py
- cp_library/test/unittest_helper.py
Code
# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
import pytest
import random
class TestBIT3:
def test_basic_operations(self):
"""Test basic BIT3 operations"""
values = [(1, 10, 100), (2, 20, 200), (3, 30, 300), (4, 40, 400)]
bit = BIT3(values)
assert len(bit) == 4
assert bit[0] == (1, 10, 100)
assert bit[1] == (2, 20, 200)
assert bit[2] == (3, 30, 300)
assert bit[3] == (4, 40, 400)
assert bit.sum(1) == (1, 10, 100)
assert bit.sum(2) == (3, 30, 300)
assert bit.sum(3) == (6, 60, 600)
assert bit.sum(4) == (10, 100, 1000)
def test_sum_range(self):
"""Test range sum operations"""
values = [(1, 10, 100), (2, 20, 200), (3, 30, 300), (4, 40, 400)]
bit = BIT3(values)
assert bit.sum_range(0, 2) == (3, 30, 300)
assert bit.sum_range(1, 3) == (5, 50, 500)
assert bit.sum_range(2, 4) == (7, 70, 700)
assert bit.sum_range(0, 4) == (10, 100, 1000)
def test_add_operations(self):
"""Test add operations"""
bit = BIT3(4, (0, 0, 0))
bit.add(0, (1, 10, 100))
bit.add(1, (2, 20, 200))
assert bit.sum(2) == (3, 30, 300)
bit.add(1, (1, 10, 100)) # Add more to index 1
assert bit.sum(2) == (4, 40, 400)
from cp_library.ds.tree.bit.bit3_cls import BIT3
if __name__ == '__main__':
from cp_library.test.unittest_helper import run_verification_helper_unittest
run_verification_helper_unittest()# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
import pytest
import random
class TestBIT3:
def test_basic_operations(self):
"""Test basic BIT3 operations"""
values = [(1, 10, 100), (2, 20, 200), (3, 30, 300), (4, 40, 400)]
bit = BIT3(values)
assert len(bit) == 4
assert bit[0] == (1, 10, 100)
assert bit[1] == (2, 20, 200)
assert bit[2] == (3, 30, 300)
assert bit[3] == (4, 40, 400)
assert bit.sum(1) == (1, 10, 100)
assert bit.sum(2) == (3, 30, 300)
assert bit.sum(3) == (6, 60, 600)
assert bit.sum(4) == (10, 100, 1000)
def test_sum_range(self):
"""Test range sum operations"""
values = [(1, 10, 100), (2, 20, 200), (3, 30, 300), (4, 40, 400)]
bit = BIT3(values)
assert bit.sum_range(0, 2) == (3, 30, 300)
assert bit.sum_range(1, 3) == (5, 50, 500)
assert bit.sum_range(2, 4) == (7, 70, 700)
assert bit.sum_range(0, 4) == (10, 100, 1000)
def test_add_operations(self):
"""Test add operations"""
bit = BIT3(4, (0, 0, 0))
bit.add(0, (1, 10, 100))
bit.add(1, (2, 20, 200))
assert bit.sum(2) == (3, 30, 300)
bit.add(1, (1, 10, 100)) # Add more to index 1
assert bit.sum(2) == (4, 40, 400)
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
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 list3(Generic[_T1, _T2, _T3]):
__slots__ = 'A1', 'A2', 'A3'
def __init__(lst, A1: list[_T1], A2: list[_T2], A3: list[_T3]):
lst.A1, lst.A2, lst.A3 = A1, A2, A3
def __len__(lst): return len(lst.A1)
def __getitem__(lst, i: int): return lst.A1[i], lst.A2[i], lst.A3[i]
def __setitem__(lst, i: int, v: tuple[_T1, _T2, _T3]): lst.A1[i], lst.A2[i], lst.A3[i] = v
def __contains__(lst, v: tuple[_T1, _T2, _T3]): raise NotImplementedError
def index(lst, v: tuple[_T1, _T2, _T3]): raise NotImplementedError
def reverse(lst): lst.A1.reverse(); lst.A2.reverse(); lst.A3.reverse()
def sort(lst, reverse=False): isort_parallel(lst.A1, lst.A2, lst.A3, reverse=reverse)
def pop(lst): return lst.A1.pop(), lst.A2.pop(), lst.A3.pop()
def append(lst, v: tuple[_T1, _T2, _T3]):
v1, v2, v3 = v
lst.A1.append(v1); lst.A2.append(v2); lst.A3.append(v3)
def add(lst, i: int, v: tuple[_T1, _T2, _T3]): lst.A1[i] += v[0]; lst.A2[i] += v[1]; lst.A3[i] += v[2]
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 BIT3(BITBase[_T]):
_lst = list3
K = 3
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]
def _sub(bit, a, b): return a[0] - b[0], a[1] - b[1], a[2] - b[2]
if __name__ == '__main__':
"""
Helper for making unittest files compatible with verification-helper.
This module provides a helper function to run a dummy Library Checker test
so that unittest files can be verified by oj-verify.
"""
def run_verification_helper_unittest():
"""
Run a dummy AOJ ITP1_1_A test for verification-helper compatibility.
This function should be called in the __main__ block of unittest files
that need to be compatible with verification-helper.
The function:
1. Prints "Hello World" (AOJ ITP1_1_A solution)
2. Runs pytest for the calling test file
3. Exits with the pytest result code
"""
import sys
# Print "Hello World" for AOJ ITP1_1_A problem
print("Hello World")
import io
from contextlib import redirect_stdout, redirect_stderr
# Capture all output during test execution
output = io.StringIO()
with redirect_stdout(output), redirect_stderr(output):
# Get the calling module's file path
frame = sys._getframe(1)
test_file = frame.f_globals.get('__file__')
if test_file is None:
test_file = sys.argv[0]
result = pytest.main([test_file])
if result != 0:
print(output.getvalue())
sys.exit(result)
run_verification_helper_unittest()