Segment Trees & BIT
Lazy propagation, segment tree beats, and Fenwick tree applications through 10 problems.
Lessons
1. Introduction to Segment Trees and BIT
Range queries and updates
2. Techniques Overview
What you'll learn
3. Codeforces 380C Sereja and Brackets - Problem Statement
CF 380C - bracket subsequence queries
4. Codeforces 380C Sereja and Brackets - Solution
Custom merge function
5. Codeforces 380C Sereja and Brackets - Implementation
Build and query with custom merge
6. Codeforces 380C Sereja and Brackets - Example and Complexity Analysis
Standard segment tree bounds
7. Codeforces 52C Circular RMQ - Problem Statement
CF 52C - range min with circular queries
8. Codeforces 52C Circular RMQ - Solution
Handle circular with two queries
9. Codeforces 52C Circular RMQ - Implementation
Lazy propagation template
10. Codeforces 52C Circular RMQ - Example and Complexity Analysis
Logarithmic with lazy
11. Codeforces 558E A Simple Task - Problem Statement
CF 558E - sort substrings
12. Codeforces 558E A Simple Task - Solution
One segment tree per letter
13. Codeforces 558E A Simple Task - Implementation
26 trees with lazy assignment
14. Codeforces 558E A Simple Task - Example and Complexity Analysis
26 times log factor
15. Codeforces 914D Bash and a Tough Math Puzzle - Problem Statement
CF 914D - GCD range queries
16. Codeforces 914D Bash and a Tough Math Puzzle - Why Naive Fails
Linear GCD is too slow
17. Codeforces 914D Bash and a Tough Math Puzzle - Solution
Count bad elements
18. Codeforces 914D Bash and a Tough Math Puzzle - Implementation
GCD segment tree with counting
19. Codeforces 914D Bash and a Tough Math Puzzle - Example and Complexity Analysis
Logarithmic with early exit
20. Codeforces 446C DZY Loves Fibonacci Numbers - Problem Statement
CF 446C - add Fibonacci to range
21. Codeforces 446C DZY Loves Fibonacci Numbers - Why Naive Fails
Adding element by element is slow
22. DZY Loves Fibonacci Numbers - Key Insight
Fibonacci sequence properties for lazy propagation
23. Codeforces 446C DZY Loves Fibonacci Numbers - Solution
Store first two Fibonacci terms
24. Codeforces 446C DZY Loves Fibonacci Numbers - Implementation
Lazy with Fibonacci pairs
25. Codeforces 446C DZY Loves Fibonacci Numbers - Example and Complexity Analysis
Logarithmic with math
26. Codeforces 438D The Child and Sequence - Problem Statement
CF 438D - modulo range update
27. Codeforces 438D The Child and Sequence - Solution
Track maximum to skip
28. Codeforces 438D The Child and Sequence - Implementation
Segment tree beats template
29. Codeforces 438D The Child and Sequence - Example and Complexity Analysis
Amortized logarithmic
30. Codeforces 459D Pashmak and Parmida's problem - Problem Statement
CF 459D - count inversions of frequencies
31. Codeforces 459D Pashmak and Parmida's problem - Solution
BIT for inversion counting
32. Codeforces 459D Pashmak and Parmida's problem - Implementation
BIT for counting inversions
33. Codeforces 61E Enemy is weak - Problem Statement
CF 61E - count decreasing triples
34. Codeforces 61E Enemy is weak - Solution
Two BITs for left and right counts
35. Codeforces 61E Enemy is weak - Implementation
Coordinate compression and two passes
36. Codeforces 540E Infinite Inversions - Problem Statement
CF 540E - inversions after swaps
37. Codeforces 540E Infinite Inversions - Why Naive Fails
Infinite positions
38. Infinite Inversions - Key Insight
Gap contribution for unchanged positions
39. Codeforces 540E Infinite Inversions - Solution
Compress and count gaps
40. Codeforces 540E Infinite Inversions - Implementation
Handle gaps between affected positions
41. Codeforces 540E Infinite Inversions - Example and Complexity Analysis
Based on swap count
42. Codeforces 474E Pillars - Problem Statement
CF 474E - longest subsequence with gap constraint
43. Codeforces 474E Pillars - Solution
Segment tree for range max DP
44. Codeforces 474E Pillars - Implementation
Segment tree range max queries
45. Quiz: Segment Trees and BIT
Test your understanding
46. Section Recap
What you've learned