# rampageli/cp-templates architecture

> Architecture diagram of the GitHub repository rampageli/cp-templates, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2025-03-31). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/rampageli/cp-templates
- Repository: https://github.com/rampageli/cp-templates

## Overview

##### Main components
- Basic Algorithms: Contains implementations for prefix and difference arrays and hashing techniques.
- Dynamic Programming (dp): Includes several DP strategies (e.g., tree DP, digit DP, knapsack, state compression, and tree re-rooting).
- Graph Algorithms: Features various graph-related implementations – BFS (including bidirectional and multi-source variants), Dijkstra, cycle detection, topological sorting, union-find.
- Mathematical Algorithms (math): Covers prime number generation (Sieve of Eratosthenes), greatest common divisor, prime factorization, modulo operations, and more.
- String Processing: Contains algorithms like longest common prefix (LCP), sequence detection, KMP for pattern matching, and string hashing.
- Tree Algorithms: Implements binary indexed trees (BIT), lowest common ancestor (LCA) calculations, and several variants of segment trees (both static and dynamic, with lazy propagation).
- Utilities (utlils): Provides helper scripts and templates such as input templates for programming contests, additional JavaScript scripts for competitive platforms, and tree construction utilities.

##### Relationships and interactions
- Interactions between different algorithm categories if applicable – for example, graph algorithms sometimes are built on basic data structures or may use utility functions.

##### Architectural patterns and design principles
- Modular Organization: Each major algorithm category lives in its own directory. This separation adheres to clean modular design, easing both understanding and maintenance.
- Reusability and Utility Sharing: The “utlils” directory encapsulates common functionalities (like input formatting and JavaScript snippets for different competitive programming platforms), which serve as foundational dependencies for the various algorithm implementations.

##### Relevant technologies, frameworks, or libraries

- Clear labels for every cluster/component with headings like “Dynamic Programming,” “Graph Algorithms,” “Utilities,” etc.

## Diagram (Mermaid)

```mermaid
flowchart TD

    %% Basic Algorithms Cluster
    subgraph "Basic Algorithms"
        BA_main["Basic Algorithms"]:::python
        BA1["diff_matrix"]:::python
        BA2["前缀与差分"]:::python
        BA3["哈希"]:::python
    end

    %% Dynamic Programming Cluster
    subgraph "Dynamic Programming (dp)"
        DP_main["Dynamic Programming"]:::python
        dp1["换根dp"]:::python
        dp2["数位dp"]:::python
        dp3["最长递增子序列"]:::python
        dp4["树形dp"]:::python
        dp5["状压"]:::python
        dp6["背包问题"]:::python
    end

    %% Graph Algorithms Cluster
    subgraph "Graph Algorithms"
        GA_main["Graph Algorithms"]:::python
        ga1["bfs"]:::python
        ga2["dijkstra"]:::python
        ga3["find_cycle"]:::python
        ga4["topo_sort"]:::python
        ga5["union_find"]:::python
    end

    %% Mathematical Algorithms Cluster
    subgraph "Mathematical Algorithms (math)"
        MA_main["Mathematical Algorithms"]:::python
        ma1["eratosthenes"]:::python
        ma2["gcd"]:::python
        ma3["get_prime_factor"]:::python
        ma4["is_prime"]:::python
        ma5["primeTable"]:::python
        ma6["模运算"]:::python
    end

    %% String Processing Cluster
    subgraph "String Processing"
        SP_main["String Processing"]:::python
        sp1["LCP"]:::python
        sp2["is_sequence"]:::python
        sp3["kmp"]:::python
        sp4["string_hash"]:::python
    end

    %% Tree Algorithms Cluster
    subgraph "Tree Algorithms"
        TA_main["Tree Algorithms"]:::python
        ta1["BIT"]:::python
        ta2["LCA"]:::python
        ta3["SegmentTree"]:::python
        ta4["线段树"]:::python
    end

    %% Utilities Cluster
    subgraph "Utilities"
        U_main["Utilities"]:::js
        u1["inputTemplate"]:::js
        u2["jsScript"]:::js
        u3["segmentTree"]:::js
        u4["treeContructor"]:::js
    end

    %% Relationships Between Clusters
    BA_main -->|"uses"| U_main
    DP_main -->|"uses"| U_main
    GA_main -->|"uses"| U_main
    MA_main -->|"uses"| U_main
    SP_main -->|"uses"| U_main
    TA_main -->|"uses"| U_main

    GA_main -->|"builds-on"| BA_main

    %% Click Events for Basic Algorithms
    click BA_main "https://github.com/rampageli/cp-templates/tree/master/basic"
    click BA1 "https://github.com/rampageli/cp-templates/tree/master/basic/diff_matrix"
    click BA2 "https://github.com/rampageli/cp-templates/tree/master/basic/前缀与差分"
    click BA3 "https://github.com/rampageli/cp-templates/tree/master/basic/哈希"

    %% Click Events for Dynamic Programming
    click DP_main "https://github.com/rampageli/cp-templates/tree/master/dp"
    click dp1 "https://github.com/rampageli/cp-templates/tree/master/dp/换根dp"
    click dp2 "https://github.com/rampageli/cp-templates/tree/master/dp/数位dp"
    click dp3 "https://github.com/rampageli/cp-templates/tree/master/dp/最长递增子序列"
    click dp4 "https://github.com/rampageli/cp-templates/tree/master/dp/树形dp"
    click dp5 "https://github.com/rampageli/cp-templates/tree/master/dp/状压"
    click dp6 "https://github.com/rampageli/cp-templates/tree/master/dp/背包问题"

    %% Click Events for Graph Algorithms
    click GA_main "https://github.com/rampageli/cp-templates/tree/master/graph"
    click ga1 "https://github.com/rampageli/cp-templates/tree/master/graph/bfs"
    click ga2 "https://github.com/rampageli/cp-templates/tree/master/graph/dijkstra"
    click ga3 "https://github.com/rampageli/cp-templates/tree/master/graph/find_cycle"
    click ga4 "https://github.com/rampageli/cp-templates/tree/master/graph/topo_sort"
    click ga5 "https://github.com/rampageli/cp-templates/tree/master/graph/union_find"

    %% Click Events for Mathematical Algorithms
    click MA_main "https://github.com/rampageli/cp-templates/tree/master/math"
    click ma1 "https://github.com/rampageli/cp-templates/tree/master/math/eratosthenes"
    click ma2 "https://github.com/rampageli/cp-templates/tree/master/math/gcd"
    click ma3 "https://github.com/rampageli/cp-templates/tree/master/math/get_prime_factor"
    click ma4 "https://github.com/rampageli/cp-templates/tree/master/math/is_prime"
    click ma5 "https://github.com/rampageli/cp-templates/tree/master/math/primeTable"
    click ma6 "https://github.com/rampageli/cp-templates/tree/master/math/模运算"

    %% Click Events for String Processing
    click SP_main "https://github.com/rampageli/cp-templates/tree/master/string"
    click sp1 "https://github.com/rampageli/cp-templates/tree/master/string/LCP"
    click sp2 "https://github.com/rampageli/cp-templates/tree/master/string/is_sequence"
    click sp3 "https://github.com/rampageli/cp-templates/tree/master/string/kmp"
    click sp4 "https://github.com/rampageli/cp-templates/tree/master/string/string_hash"

    %% Click Events for Tree Algorithms
    click TA_main "https://github.com/rampageli/cp-templates/tree/master/tree"
    click ta1 "https://github.com/rampageli/cp-templates/tree/master/tree/BIT"
    click ta2 "https://github.com/rampageli/cp-templates/tree/master/tree/LCA"
    click ta3 "https://github.com/rampageli/cp-templates/tree/master/tree/SegmentTree"
    click ta4 "https://github.com/rampageli/cp-templates/tree/master/tree/线段树"

    %% Click Events for Utilities
    click U_main "https://github.com/rampageli/cp-templates/tree/master/utlils"
    click u1 "https://github.com/rampageli/cp-templates/tree/master/utlils/inputTemplate"
    click u2 "https://github.com/rampageli/cp-templates/tree/master/utlils/jsScript"
    click u3 "https://github.com/rampageli/cp-templates/tree/master/utlils/segmentTree"
    click u4 "https://github.com/rampageli/cp-templates/tree/master/utlils/treeContructor"

    %% Styles
    classDef python fill:#AED6F1,stroke:#1F618D,stroke-width:2px;
    classDef js fill:#F9E79F,stroke:#B7950B,stroke-width:2px;
```
