README
¶
Go Competitive Programming Templates
To navigate or import the specific components of this repository directly, utilize the primary reference index below. Each structure links directly to its source implementation.
Repository Navigation Index
- Core Collections & Utilities
- Advanced Tree Structures
- Graph & Advanced Relations
- Advanced Query & Sequence Processing
- Graph & Network Optimization
- String Processing & Automata
- Graph Flow & Combinatorial Topology
- Mathematical & Specialized Query Optimizations
- Geometric Optimizations & Persistent Queries
- Advanced Algebraic & Matrix Computations
- Advanced Self-Balancing Systems
- Backward Compatibility
Repository Metadata & Verification
| Property | Value / Status | Description |
|---|---|---|
| Module Path | github.com/Roonil03/Templates_GoLang |
Canonical Go module import string |
| Go Compliance | >= go 1.21 |
Supports generic type parameters and cmp.Ordered |
| Legacy Support | go 1.20 and below |
Contained inside isolated local subdirectory |
| Ecosystem Status | Stable / Production-Ready | Verified algorithms optimized for compilation footprint |
| Stability Level | v1.x.x Series | Strict SemVer adherence across structural interfaces |
A formal, high-performance library of advanced data structures optimized for competitive programming and complex algorithmic tasks in Go. Every root structure is fully type-safe, leveraging Go Generics to allow flexible map-like and collection-level templating.
Algorithmic Complexity Reference
| Structure | Time Complexity | Space Complexity |
|---|---|---|
| Deque | $O(1)$ push/pop | $O(n)$ |
| Segment Tree | $O(\log n)$ query/update | $O(n)$ |
| Fenwick Tree (BIT) | $O(\log n)$ query/update | $O(n)$ |
| 2D Fenwick Tree | $O(\log^2 n)$ query/update | $O(n^2)$ |
| Treap | $O(\log n)$ expected | $O(n)$ |
| Disjoint Set Union (DSU) | $O(\alpha(n))$ amortized | $O(n)$ |
| Rope | $O(\log n)$ split/concat | $O(n)$ |
| Euler Tour | $O(1)$ ancestor check | $O(n)$ |
| LRU Cache | $O(1)$ get/put | $O(\text{capacity})$ |
| Priority Queue / Heap | $O(\log n)$ push/pop | $O(n)$ |
| Sparse Table | $O(n \log n)$ init / $O(1)$ query | $O(n \log n)$ |
| Trie | $O(L)$ insertion / search | $O(L \cdot \Sigma)$ |
| PBDS (Order Stats Tree) | $O(\log n)$ insert / query | $O(n)$ |
| Heavy-Light Decomposition | $O(n)$ build / $O(\log^2 n)$ query | $O(n)$ |
| Suffix Array (with LCP) | $O(n \log n)$ or $O(n \log^2 n)$ build | $O(n)$ |
| Dijkstra's Algorithm | $O((V + E) \log V)$ | $O(V + E)$ |
| Bellman-Ford Algorithm | $O(V \cdot E)$ | $O(V + E)$ |
| Floyd-Warshall Algorithm | $O(V^3)$ | $O(V^2)$ |
| Kruskal's MST | $O(E \log E)$ | $O(V + E)$ |
| Prim's MST | $O(E \log V)$ | $O(V + E)$ |
| Tarjan's SCC | $O(V + E)$ | $O(V)$ |
| Dinic's Maxflow | $O(V^2 E)$ | $O(V + E)$ |
| Kahn's Algorithm | $O(V + E)$ | $O(V + E)$ |
| Kadane's Algorithm | $O(n)$ | $O(1)$ |
| KMP Matcher | $O(n + m)$ | $O(m)$ |
| Modular Power | $O(\log \text{power})$ | $O(1)$ |
| Rabin-Karp Hashing | $O(n + m)$ average | $O(1)$ |
| Suffix Automaton | $O(n \cdot \Sigma)$ | $O(n \cdot \Sigma)$ |
| Mo's Algorithm | $O((n + q) \sqrt{n})$ | $O(q)$ |
| Convex Hull Trick | $O(\log n)$ query / insert | $O(n)$ |
| Persistent Segment Tree | $O(\log n)$ query / update | $O(n + q \log n)$ |
| Lazy Segment Tree | $O(\log n)$ range query / update | $O(n)$ |
| Matrix Multiplication (D&C) | $O(n^3)$ or $O(n^{\log_2 7})$ block scaling | $O(n^2)$ |
| Gaussian Elimination | $O(n^3)$ | $O(n^2)$ |
| Fibonacci Heap | $O(1)$ insert/decrease-key / $O(\log n)$ delete | $O(n)$ |
| Red-Black Tree | $O(\log n)$ search / insert / delete | $O(n)$ |
Competitive Programming Integration
Standard Import
For local modular development or automated build test runners:
go get github.com/Roonil03/Templates_GoLang/segment_tree
Direct Submission Strategy (Online Judges)
For platforms requiring a unified source submission file (e.g., Codeforces, LeetCode, CodeChef), copy the targeted structural definition blocks and associated pointer receiver methods directly into your main compilation file. The removal of unnecessary boilerplate ensures compatibility with code limits.
package main
import (
"cmp"
"fmt"
)
// Example copy-paste deployment for an Online Judge
type PriorityQueue[T cmp.Ordered] struct {
data []T
}
func NewPriorityQueue[T cmp.Ordered]() *PriorityQueue[T] {
return &PriorityQueue[T]{data: make([]T, 0)}
}
func main() {
pq := NewPriorityQueue[int]()
// Competitive execution loop goes here
fmt.Println(pq)
}
Directories
Click to show internal directories.
Click to hide internal directories.