ds

Data Structure

Disjoint Set Union

🚧WIP
a.k.a Union Find Tree

Challenges

• 道路の老朽化対策について - AtCoder ABC040D
• D - Friend Suggestions

Binary Indexed Tree

Binary Indexed Tree (Fenwick Tree) is a data structure.

• It can calculate a cumulative function in the given range [l,r) in O(logN).

• It can update an element of A in O(logN).

• Binary Indexed Tree | C++ code

• Binary Indexed Tree 2D | C++ code

References in English

• Binary Indexed Trees
• Fenwick Tree - Competitive Programming Algorithms

References in Japanese

• Binary Indexed Tree のはなし

Challenges

• F - Range Set Query

MinMax Queue

A data structure that allows to store and retrieve elements in a first-in-first-out (FIFO) fashion. This data structure also allows to retrieval of the minimum and maximum value efficiently.

MinMax Stack

A data structure that allows to store and retrieve elements in a last-in-first-out (LIFO) fashion. This data structure also allows to retrieval of the minimum and maximum value efficiently.

Randomized Heap

🚧WIP

Segment Tree

🚧WIP

Challenges

• E - Simple String Queries

Sqrt Decomposition

🚧WIP

Sparse Table

🚧WIP

Disjoint Sparse Table

🚧WIP

Treap

🚧WIP

Implicit Treap

🚧WIP

kD Tree

🚧WIP