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 306 / 312 1400
Point update, minimum query 272 / 280 1400
Range update, sum query 250 / 271 1400
Range update, minimum query 231 / 238 1400
Apple picking 156 / 185 1500
Non-negative subarray 153 / 177 1500
Inversions 144 / 147 1500
K-query 168 / 175 1500
Divisible by 3 144 / 161 1500
Mushroom harvesting 84 / 88 1500
KSS 64 / 79 1500
D-query 128 / 141 1600
Greatest subarray sum 110 / 121 1600
Copying data 78 / 81 1600
Within 1 71 / 82 1600
Within 2 67 / 72 1600
Ladder update 82 / 91 1700
Racing 40 / 44 1700
One time 53 / 69 1800
Subarray XOR 52 / 57 1800
String sorting 52 / 72 1900
Odd query 13 / 16 2000