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 298 / 304 1400
Point update, minimum query 263 / 270 1400
Range update, sum query 242 / 261 1400
Range update, minimum query 225 / 231 1400
Apple picking 151 / 181 1500
Non-negative subarray 149 / 173 1500
Inversions 142 / 145 1500
K-query 163 / 170 1500
Divisible by 3 140 / 159 1500
Mushroom harvesting 84 / 88 1500
KSS 62 / 77 1500
D-query 126 / 140 1600
Greatest subarray sum 107 / 117 1600
Copying data 76 / 79 1600
Within 1 70 / 81 1600
Within 2 66 / 71 1600
Ladder update 78 / 86 1700
Racing 40 / 44 1700
One time 53 / 67 1800
Subarray XOR 50 / 55 1800
String sorting 52 / 72 1900
Odd query 13 / 16 2000