cp_library/ds/min_sparse_table_cls.py

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+09:00

Depends on

• cp_library/alg/dp/min2_fn.py

Required by

• cp_library/alg/tree/fast/aux_tree_base_cls.py
• cp_library/alg/tree/fast/aux_tree_cls.py
• cp_library/alg/tree/fast/aux_tree_weighted_cls.py
• cp_library/alg/tree/lca_table_iterative_cls.py
• cp_library/alg/tree/lca_table_weighted_iterative_cls.py
• cp_library/alg/tree/tree_cls.py
• cp_library/alg/tree/tree_proto.py
• cp_library/alg/tree/tree_weighted_cls.py
• cp_library/alg/tree/tree_weighted_proto.py

Verified with

• test/aoj/grl/grl_5_a_diameter.test.py
• test/aoj/grl/grl_5_c_lca_table_iterative.test.py
• test/aoj/vol/0439_aux_dijkstra.test.py
• test/aoj/vol/0439_aux_rerooting_dp.test.py
• test/aoj/vol/0439_aux_weighted_rerooting_dp.test.py
• test/atcoder/abc/abc202_e_dfs_enter_leave.test.py
• test/atcoder/abc/abc294_g_fast_tree_lca_table_weighted_bit.test.py
• test/atcoder/abc/abc361_e_tree_diameter.test.py
• test/atcoder/dp/dp_v_subtree_rerooting_iterative.test.py
• test/atcoder/dp/dp_v_subtree_rerooting_recursive.test.py
• test/library-checker/data-structure/staticrmq.test.py
• test/library-checker/tree/jump_on_tree.test.py
• test/library-checker/tree/lca.test.py
• test/yukicoder/3407.test.py

Code

import cp_library.__header__
# from typing import Generic
# from cp_library.misc.typing import _T
from cp_library.alg.dp.min2_fn import min2

import cp_library.ds.__header__

class MinSparseTable:
    def __init__(st, arr: list):
        st.N = N = len(arr)
        st.log = N.bit_length()
        st.data = data = [0] * (st.log*N)
        data[:N] = arr 
        for i in range(1,st.log):
            a, b, c = i*N, (i-1)*N, (i-1)*N + (1 << (i-1))
            for j in range(N - (1 << i) + 1):
                data[a+j] = min2(data[b+j], data[c+j])

    def query(st, l: int, r: int):
        k = (r-l).bit_length() - 1
        return min2(st.data[k*st.N + l], st.data[k*st.N + r - (1<<k)])
    

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''
# from typing import Generic
# from cp_library.misc.typing import _T


def min2(a, b):
    return a if a < b else b



class MinSparseTable:
    def __init__(st, arr: list):
        st.N = N = len(arr)
        st.log = N.bit_length()
        st.data = data = [0] * (st.log*N)
        data[:N] = arr 
        for i in range(1,st.log):
            a, b, c = i*N, (i-1)*N, (i-1)*N + (1 << (i-1))
            for j in range(N - (1 << i) + 1):
                data[a+j] = min2(data[b+j], data[c+j])

    def query(st, l: int, r: int):
        k = (r-l).bit_length() - 1
        return min2(st.data[k*st.N + l], st.data[k*st.N + r - (1<<k)])
    

Back to top page