Fenwick Tree

Motivation Given a list of elements, we want to calculate cumulative total based on an associative binary operation. Moreover, efficient modification is desired. Naive Concept Using an array arr to store each element in the original list.

Disjoint Sets

Motivation Design a data structure that stores a partition of a set. With the operations of union, find, etc. Naive Way-A: Update the Set Each Element Belongs to Find: $O(1)$ Make Union: $O(N)$

Segment Tree

Range Minimum (Maximum) Query class SegmentTree { public: SegmentTree(size_t size) : N(size), arr(size << 2, 0), tag(size << 2, 0) {} int query(int left, int right) { return query(1, 1, N, left, right); } void modify(int left, int right, int val) {

BigInteger