Rafid

\documentclass[twoside]{book}
\usepackage[utf8]{inputenc}
\usepackage{geometry}
\geometry{a4paper, bottom=1in, right=1in, left=1.5in, top=1in}
\usepackage{url}
\usepackage{minted}
\usepackage{amsmath}
\usepackage[toc,page]{appendix}

\setminted{linenos, tabsize=4, breaklines, frame=lines, framesep=2mm}
\usemintedstyle{perldoc}
% \usemintedstyle{bw}

% errors
\DeclareUnicodeCharacter{2264}{ }
\DeclareUnicodeCharacter{2200}{ }

\title{{\Huge{T E M P L A T E S}}}
\author{\Large{R A F I D}}
\date{} % Nov 13, 2019

\begin{document}

\maketitle

\tableofcontents
% \pagebreak


\begin{chapter}{Data Structures}
    \section{Binary Indexed Tree}
    Faster than Segment Tree. Useful if query $Q(l, r) \equiv Q(1, r) \setminus Q(1, l-1)$.
    \inputminted{cpp}{src/ds/binary-indexed-tree-bit.cc}

    \section{Centroid Decomposition}
    For a given tree, reconstructs the tree such that height is at most $O(\log n)$. Also, consider any two arbitrary vertices $A$ and $B$ and the path between them (in the original tree) can be broken down into $A-C$ and $C-B$ where $C$ is LCA of $A$ and $B$ in the centroid tree.
    \inputminted{cpp}{src/ds/centroid-decomposition.cc}

    \section{Heavy Light Decomposition}
    Decomposes a tree to a set of paths. A path $u-v$ uses at most $\log N$ paths. Useful for path updates, subtree update and path query.
    \inputminted{cpp}{src/ds/heavy-light-decomposition-hld.cc}

    \section{Lowest Common Ancestor}
    \inputminted{cpp}{src/ds/lca-sparse-table.cc}

    \section{Mo's algorithm}
    Useful for answering offline range queries in $O((N+Q)\sqrt{N})$.
    \inputminted{cpp}{src/ds/mo.cc}

    \section{Segment Tree}

    \subsection{Lazy Propagation}
    \inputminted{cpp}{src/ds/segment-tree-lazy.cc}

    \subsection{Point Update Range Query}
    \inputminted{cpp}{src/ds/segment-tree-purq.cc}

    \section{Trie}
    \inputminted{cpp}{src/ds/trie.cc}
\end{chapter}

\begin{chapter}{Dynamic Programming}
    \section{Convex Hull Trick}
    For a given set of lines $y = m_i x + c_i$, maintains the lower (or upper) hull.

    \subsection{Dynamic (General)}
    Finds the minimum (or maximum) $y$ for a query $x$ in $O(\log N)$ time.
    \inputminted{cpp}{src/dp/convex-hull-trick-dynamic.cc}

    \subsection{Special Case}
    For lines with non-increasing slope, a bunch of sorted queries can be answered in constant time on the fly.
    \begin{equation*}
        dp(i) = \min\limits_{j<i} \{dp(j) + b(j) \cdot a(i)\}
    \end{equation*}
    Condition: $b(j) \geq b(j+1)$ and $a(i) \leq a(i+1)$ \\
    Complexity: $O(n)$ \\
    \begin{equation*}
        dp(i, j) = \min\limits_{k<j} \{dp(i-1, k) + b(k) \cdot a(j)\}
    \end{equation*}
    Condition: $b(k) \geq b(k+1)$ and $a(j) \leq a(j+1)$ \\
    Complexity: $O(kn)$

    \inputminted{cpp}{src/dp/convex-hull-trick-special.cc}

    \section{Divide \& Conquer Optimization}
    \begin{equation*}
        dp(i, j) = \min \limits_{k \leq j} \{ dp(i-1, k) + C(, j) \}
    \end{equation*}
    Let $opt(i,j)$ be the value of k that minimizes the above expression. If $opt(i, j) \leq opt(i, j+1)$, we can optimize to $O(nm \log n)$ from $O(nm^2)$ where $1 \leq i \leq n$ and $1 \leq j \leq m$.
    \inputminted{cpp}{src/dp/divide-conquer-dp.cc}

    \section{Subset over Sum (SOS DP)}
    \inputminted{cpp}{src/dp/sos-dp.cc}
\end{chapter}