🚀 DSA-Playground

           

A high-performance laboratory for mastering Data Structures and Algorithms. This repository features industrial-grade templates, optimized competitive programming solutions, and structured implementations.

🗺️ Repository Map

Tip

Click on the icons or headers to navigate to the specific modules.

🎯 CP31-Sheet Progressive problem-solving through the CP-31 curated list. D800 - D1200: Foundation D1300 - D1900: Intermediate/Advanced	⚙️ Implementations Modular, reusable templates for core DSA. Graphs: Shortest Paths, MST, Flow Trees: Segment Trees, Splay Trees
🧩 Solved Problems Collection of solutions from various OJs. LeetCode / SPOJ / Timus Archived: Legacy/Offline problems	📚 Standard Problems The "Must-Do" classics categorized by topic. Dynamic Programming patterns Array manipulation & Logic

📜 Competitive Programming Template

To maintain high performance and code clarity, all competitive programming solutions in this repository utilize a Triple-Layer Architecture. This decouples I/O stream synchronization from the core algorithmic logic.

🛠️ Implementation Deep-Dive

🌲 Trees & Advanced Data Structures

Our implementations focus on cache efficiency and generic usability.

• Segment Tree: Supports vEB (van Emde Boas) layout for better CPU cache locality. Level-aware combine logic allows for complex range queries.

Note

Performance Optimization (vEB Layout): By arranging nodes in a van Emde Boas layout, this implementation significantly reduces CPU cache misses compared to the traditional $2i$ and $2i+1$ indexing. In large-scale benchmarks ($N > 10^5$), this results in a 10–30% speedup for range queries.

• Splay Tree: A self-adjusting BST that moves frequently accessed nodes to the root.

🕸️ Graph Algorithms

• Shortest Path: Dijkstra, Bellman-Ford
• MST: Prim's, Kruskal's
• Connectivity: Kosaraju (SCC)

📊 Performance & Complexity

Template	Build	Query	Space
Segment Tree	$O(n)$	$O(\log n)$	$O(n)$
Splay Tree	$O(n \log n)$	$O(\log n)^*$	$O(n)$

* Denotes amortized time complexity.

---

🚀 Quick Start

1. Range Queries with Segment Tree

Our Segment Tree is highly flexible, allowing for custom combine logic and level-aware operations.

// Example: Range Sum
std::vector<int> arr = {1, 2, 3, 4, 5};
SegmentTree<int> st(arr); 

int sum = st.query(1, 3); // Returns 9 (2 + 3 + 4)
st.update(2, 10);         // Update index 2 to value 10

2. Dynamic Sets with Splay Tree

The Splay Tree is ideal for scenarios where recently accessed elements need to be retrieved quickly.

// Example: Self-adjusting BST
SplayTree tree = {10, 20, 30, 40};

tree.insert(25);      // Inserts 25 and splays it to the root
bool found = tree.contains(20); // Moves 20 to the root if found
tree.erase(30);       // Removes 30 and restructures optimally