Module Introduction to Segment Tree and Binary Indexed Tree

Introduction to Segment Tree and Binary Indexed Tree

**Frequency: 10/10** Segment trees and binary indexed trees (BIT) are indispensable data structures in competitive programming, enabling efficient range queries and updates over arrays. Generally speaking, Segment Tree is more versatile while BIT have a lower constant factor. Since BIT can be a bit tricky to understand at first, most people choose to start with Segment Tree. And you should choose Segment Tree too.

Resources

- [CP Algorithms: Segment Tree](https://cp-algorithms.com/data_structures/segment_tree.html) - [CP Algorithms: Fenwick Tree](https://cp-algorithms.com/data_structures/fenwick.html)

Problems

Point update, sum query 218 / 226 1400
Point update, minimum query 198 / 203 1400
Range update, sum query 183 / 200 1400
Range update, minimum query 168 / 170 1400
Apple picking 113 / 130 1500
Non-negative subarray 109 / 126 1500
Inversions 102 / 105 1500
K-query 122 / 127 1500
Divisible by 3 97 / 113 1500
Mushroom harvesting 64 / 68 1500
KSS 44 / 53 1500
D-query 98 / 107 1600
Greatest subarray sum 80 / 86 1600
Copying data 58 / 60 1600
Within 1 58 / 64 1600
Within 2 54 / 56 1600
Ladder update 58 / 62 1700
Racing 32 / 34 1700
One time 39 / 54 1800
Subarray XOR 37 / 42 1800
String sorting 38 / 53 1900
Odd query 5 / 6 2000