Segment Tree

A Segment Tree is a powerful, flexible, binary tree-based data structure used for storing information about intervals or segments. It is particularly adept at handling range queries (e.g., find the sum, minimum, or maximum over a range `[i, j]` of an array) and point updates. Each node in the segment tree represents an interval of the original array. The root represents the entire array, and its children represent the left and right halves of that interval, and so on, until the leaf nodes, which represent individual elements of the array. The value stored in an internal node is a computed value based on its children's intervals (e.g., the sum of its children's sums). This structure allows for both range queries and point updates to be performed in O(log n) time. Building the entire tree takes O(n) time. The versatility comes from the fact that the 'merge' operation can be adapted for various problems—sums, products, minimums, maximums, greatest common divisors, etc.—as long as the operation is associative. This makes segment trees a fundamental tool in competitive programming and applications requiring efficient analysis of data over dynamic ranges.