Segment tree：线段树；一种用于对数组/序列进行区间查询（如区间和、最小值、最大值）与区间更新的树形数据结构，通常能在 O(log n) 时间内完成一次查询或更新。（也常与“lazy propagation 懒标记”搭配实现区间修改）
/ˈsɛɡmənt triː/
I used a segment tree to answer range sum queries quickly.
我用线段树来快速回答区间求和查询。
After applying lazy propagation, the segment tree can handle range updates and range minimum queries efficiently even on large inputs.
加入懒标记后，线段树即使在大规模数据上也能高效处理区间更新与区间最小值查询。
“Segment”意为“片段、区间”，“tree”指“树形结构”。该术语直接描述了这种数据结构的核心：把一个整体区间不断划分为更小的子区间，并用树来组织这些区间信息，从而支持快速的区间操作。
Select Language