Segment Tree

Definitions

1. A balanced binary tree where each node stores an aggregate (sum, min, max, GCD, etc.) over a contiguous range of an array, supporting both range queries and point or range updates in O(log n) time.

   In plain English: A data structure that pre-calculates summaries (like totals or minimums) for every possible range of a list, so any range query is fast.

   Example: "We used a segment tree with lazy propagation to answer range-sum queries with interval updates in log time during the contest."

Related Terms

• Hash Map
• Hash Ring
• Hash Set
• Hashing Algorithm
• Persistent Data Structure
• Priority Queue
• Radix Tree
• Search Tree
• Skiplist
• Union Find