HEADER_LIST.md

SegmentTree

A segment tree template, supports lazy propagation (range modify, range query), you only have to implement two key functions, you can use lambda for these two functions.

• SegmentTree.h
• SegmentTree.md
• SegmentTree.cpp

SAM

A suffix automaton template which supports arbitary character type, can construct the SAM and the parent tree.

• SAM.h
• SAM.md
• SAM.cpp

BIT

A binary indexed tree (Fenwick tree) template which supports element addition, query prefix sum. You only need to implement "add two values", lambda is supported. You can clear it in O(1).

• BIT.h
• BIT.md
• BIT.cpp

MonotonousQueue

Get the maximum value in a FIFO queue in linear time.

• MonotonousQueue.h
• MonotonousQueue.md
• MonotonousQueue.cpp

ModInt

Integer modulo an number.

• ModInt.h
• ModInt.md
• ModInt.cpp

ConstantModInt

A faster ModInt with a compile-time constant modulo as a template parameter.

• ConstantModInt.h
• ConstantModInt.md
• ConstantModInt.cpp

HLD

The heavy-light decomposition of a tree. Can be used to perform operations on paths.

• HLD.h
• HLD.md
• HLD.cpp

SparseTable

Sparse table can be used to get the "sum" of an interval in O(nlogn)-O(1), where the "sum" behaves like a function of a (non-multi) set. For example, min and gcd.

• SparseTable.h
• SparseTable.md
• SparseTable.cpp