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 438 / 448 1400
Point update, minimum query 390 / 410 1400
Range update, sum query 352 / 379 1400
Range update, minimum query 335 / 342 1400
Apple picking 208 / 249 1500
Non-negative subarray 205 / 240 1500
Inversions 193 / 199 1500
K-query 215 / 231 1500
Divisible by 3 202 / 224 1500
Mushroom harvesting 111 / 119 1500
KSS 96 / 115 1500
D-query 168 / 185 1600
Greatest subarray sum 150 / 165 1600
Copying data 100 / 104 1600
Within 1 101 / 113 1600
Within 2 94 / 105 1600
Ladder update 104 / 116 1700
Racing 56 / 63 1700
One time 68 / 86 1800
Subarray XOR 71 / 76 1800
String sorting 68 / 93 1900
Odd query 21 / 27 2000
Full sequence 5 / 7 2000