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 383 / 392 1400
Point update, minimum query 338 / 356 1400
Range update, sum query 314 / 337 1400
Range update, minimum query 298 / 303 1400
Apple picking 196 / 236 1500
Non-negative subarray 190 / 223 1500
Inversions 174 / 178 1500
K-query 202 / 211 1500
Divisible by 3 186 / 206 1500
Mushroom harvesting 97 / 104 1500
KSS 88 / 106 1500
D-query 155 / 169 1600
Greatest subarray sum 136 / 148 1600
Copying data 93 / 96 1600
Within 1 88 / 101 1600
Within 2 83 / 93 1600
Ladder update 94 / 105 1700
Racing 50 / 56 1700
One time 63 / 80 1800
Subarray XOR 66 / 71 1800
String sorting 61 / 86 1900
Odd query 18 / 22 2000
Full sequence 2 / 2 2000