cp_library/ds/list/presum_cls.py

• View this file on GitHub
• Last update: 2025-06-20 03:24:59+09:00

Required by

• cp_library/ds/wavelet/wm_group_cls.py
• cp_library/ds/wavelet/wm_group_compressed_cls.py
• cp_library/ds/wavelet/wm_group_points_cls.py

Verified with

• test/library-checker/data-structure/rectangle_sum_wm_group.test.py
• test/library-checker/data-structure/rectangle_sum_wm_group_compressed.test.py
• test/library-checker/data-structure/rectangle_sum_wm_group_points.test.py
• test/library-checker/data-structure/static_rectangle_add_rectangle_sum_wm_group_points.test.py

Code

import cp_library.__header__
import cp_library.ds.__header__
import cp_library.ds.list.__header__
class Presum:
    def __init__(P, op, e, diff, A: list):
        P.N = len(A); P.op, P.e, P.diff, P.pre = op, e, diff, [e]*(P.N+1)
        for i,a in enumerate(A):P.pre[i+1]=op(P.pre[i],a)
    def __getitem__(P,i):return P.pre[i]
    def prod(P,l:int,r:int):return P.diff(P.pre[r],P.pre[l])

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''


class Presum:
    def __init__(P, op, e, diff, A: list):
        P.N = len(A); P.op, P.e, P.diff, P.pre = op, e, diff, [e]*(P.N+1)
        for i,a in enumerate(A):P.pre[i+1]=op(P.pre[i],a)
    def __getitem__(P,i):return P.pre[i]
    def prod(P,l:int,r:int):return P.diff(P.pre[r],P.pre[l])

Back to top page