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
  • Deque Implementation
  • LRU Cache Implementation
  • Priority Queue / Heap Implementation
• Advanced Tree Structures
  • Segment Tree Implementation
  • Fenwick Tree (1D BIT) Implementation
  • 2D Fenwick Tree Implementation
  • Treap Implementation
• Graph & Advanced Relations
  • Disjoint Set Union (DSU) Implementation
  • Rope Data Structure
  • Euler Tour Implementation
• Advanced Query & Sequence Processing
  • Sparse Table Implementation
  • Trie Implementation
  • Policy-Based Data Structure (PBDS)
  • Heavy-Light Decomposition (HLD)
  • Suffix Array & LCP
• Graph & Network Optimization
  • Dijkstra's Shortest Path
  • Bellman-Ford Algorithm
  • Floyd-Warshall All-Pairs
  • Kruskal's Minimum Spanning Tree
  • Prim's Minimum Spanning Tree
• String Processing & Automata
  • KMP Matcher & Prefix Function
  • Rabin-Karp Rolling Hash
  • Suffix Automaton
• Graph Flow & Combinatorial Topology
  • Tarjan's Strongly Connected Components
  • Dinic's Maxflow Algorithm
  • Kahn's Topological Sort
• Mathematical & Specialized Query Optimizations
  • Kadane's Maximum Subarray Sum
  • Modular Arithmetic & Modular Power
  • Mo's Offline Block Decomposition
• Geometric Optimizations & Persistent Queries
  • Convex Hull Trick
  • Persistent Segment Tree
  • Lazy Segment Tree
• Advanced Algebraic & Matrix Computations
  • Matrix Multiplication (Divide & Conquer)
  • Gaussian Elimination
• Advanced Self-Balancing Systems
  • Fibonacci Heap
  • Red-Black Tree
• Backward Compatibility
  • Legacy Modules (Go <= 1.20)

---

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