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.

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)$

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) {

--- tags: Data Structure title: BigInteger ---

Programming Notes Data Structure BigInteger Fenwick Tree Disjoint Sets Segment Tree

Dinic's Algorithm Sample Code struct Dinic { Dinic(size_t N, int s, int t) : N(N), s(s), t(t), adj(N) {} struct Edge { int to; int cap; int rev;

Sample Code vector<vector<int>> adj(n); vector<bool> vis(n); vector<int> times(n, -1), low(n, -1); int count = 0; int ans = 0; function<void(int, int)> dfs = [&](int u, int p) { vis[u] = true;

Prim's Algorithm Sample Code Kruskal's Algorithm $\text{Input: } G=(V,E)\text{ and a weight function }w:V\times V\rightarrow\mathbb{R}$ $\text{Output: } T=(V,F) \text{ where }F\subseteq E\text{ and }T\text{ is a spanning tree of }G.$ $1F\leftarrow\varnothing$ $2\textbf{for each }e={u,v}\text{ in }E \text{ ordered by }w(u,v)\text{ do}$ $3~~~~~~~~\textbf{if }\text{there is no cycle in }H=(V,F\cup e)\text{ do}$ $4F\leftarrow F\cup e$

Special case: 2-Dimensional space Graham's Scan First choose a trivial point $p_0$ that it must be in convex hull (leftmost and lowest). sort all the other points in polar angle order, getting ${p_1, \dots,p_n}$. let $s={p_0,p_1}={s_2,s_1}$(reversed order). let $i=2$. while $i<n$ do the following: If $|s|<2$ or $\angle p_is_1s_2$ is convex, then let $s=s\cup{p_i}$, and $i=i+1$. If not, $s=s\setminus{s_1}$.

--- tags: Geometry title: Closest Pair ---

--- tags: Graph Theory title: Lowest Common Ancestor ---

--- tags: Dynamic Programming title: Weighted Perfect Matching ---

--- tags: Dynamic Programming title: Longest Common Subsequence ---

--- tags: Dynamic Programming title: Longest Increasing Subsequence ---

Failure Function vector<int> failure_function(const string& s) { vector<int> failure(s.length(), -1); int p = -1; for (int i = 1; s[i]; ++i) { while (p != -1 && s[p + 1] != s[i]) p = failure[p]; if (s[p + 1] == s[i]) ++p;

Fractional Knapsack Problem Input: A sequence of weights and another of values, the capacity of knapsack. Output: Maximum value. (You can cut item into pieces.) Greedy Sorted by $\dfrac{\text{value}}{\text{weight}}$ of each item, always choose the biggest one in that moment. Since every unit of space in the knapsack contains the most valued item,

Problem Input: number of cites, number of roads, a sequence of roads Output: Minimum cost of travelling through all the cities. Naive: Exhaustive Search All permutation of cities. Time complexity: $O(n!)$, where $n$ is the number of cities.

--- tags: Useful Headers title: (unknown) ---

Problem Description Given a DAG (directed acyclic graph), find out a sequence ${a_1,\dots,a_n}$ such that if $i<j$, you need to go through $a_i$ before you go to $a_j$. Kahn's Algorithm vector<vector<int>> adj; vector<int> topological_sort() { int n = adj.size();

Kosaraju's Algorithm Notion: Strongly connected components will also be strongly connected in transposed graph. vector<vector<int>> adj, radj; vector<int> timeStamp, scc; vector<bool> vis; void dfs(int u) { vis[u] = true;