LeetCode Patterns ·

🎯 Segment Tree

1️⃣ Core Framework

When discussing Segment Tree, I frame it as:

What problem pattern Segment Tree solves
Range query problem
Why prefix sum is not enough
Segment tree structure
Build operation
Query operation
Update operation
Recursive implementation
Iterative implementation
Senior-level explanation

2️⃣ What Problem Are We Solving?

Segment Tree is used to answer range queries efficiently while supporting updates.

It is commonly used for:

Range sum query
Range minimum query
Range maximum query
Dynamic array updates
Mutable prefix-style queries
Count queries over ranges
Interval aggregation
Range frequency problems
Lazy propagation problems
Competitive programming range query problems

The core idea is:

Break an array into segments.
Each node stores information about one segment.
Range query combines information from relevant segments.
Update only changes affected segments.

👉 Interview Answer

A Segment Tree is a tree data structure used for efficient range queries and point updates.

Each node represents a range of the array.

The node stores aggregated information for that range, such as sum, min, or max.

It is useful when the array changes and we still need fast range queries.

3️⃣ Why Segment Tree Works

Range Query Problem

Suppose we have:

nums = [2, 4, 5, 7, 8, 9]

We want to answer:

sum from index 1 to 4

That means:

4 + 5 + 7 + 8 = 24

A brute force approach scans the range every time.

Time: O(n)

Segment Tree Idea

Segment Tree precomputes information for ranges.

Example:

[0, 5]
├── [0, 2]
│   ├── [0, 1]
│   └── [2, 2]
└── [3, 5]
    ├── [3, 4]
    └── [5, 5]

Each node stores the sum of its range.

👉 Interview Answer

Segment Tree works by recursively splitting the array into smaller ranges.

Each tree node stores the answer for one range.

A range query can be answered by combining only the nodes that fully cover parts of the query range, instead of scanning every element.

4️⃣ Why Prefix Sum Is Not Enough

Prefix Sum Works for Static Arrays

For a static array:

range_sum(left, right) = prefix[right + 1] - prefix[left]

Query is:

O(1)

Problem With Updates

If one value changes:

nums[i] = new_value

Then many prefix values after index i need to change.

Update becomes:

O(n)

Segment Tree Tradeoff

Segment Tree gives:

Query: O(log n)
Update: O(log n)

This is better when both queries and updates are frequent.

👉 Interview Answer

Prefix sum is great when the array is static.

But if the array changes, one update may require updating many prefix values.

Segment Tree is useful when we need both efficient range queries and efficient updates.

It trades O(1) static queries for O(log n) query and O(log n) update.

5️⃣ Segment Tree Structure

Basic Idea

Each node represents a range:

[start, end]

For range sum, each node stores:

sum of nums[start:end + 1]

Leaf Node

A leaf node represents one element:

[start == end]

Example:

[3, 3]

stores:

nums[3]

Internal Node

An internal node combines its children:

node.sum = left_child.sum + right_child.sum

👉 Interview Answer

In a Segment Tree, each node represents a range of the array.

A leaf node represents a single element.

An internal node stores the combined result of its left and right children.

For range sum, that combination is addition.

6️⃣ Build Operation

Purpose

Build creates the Segment Tree from the input array.

Steps:

If start == end:
    create leaf node

Otherwise:
    split range into two halves
    build left child
    build right child
    combine children

Code

class SegmentTreeNode:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.total = 0
        self.left = None
        self.right = None


def build(nums, start, end):
    if start == end:
        node = SegmentTreeNode(start, end)
        node.total = nums[start]
        return node

    mid = (start + end) // 2

    node = SegmentTreeNode(start, end)
    node.left = build(nums, start, mid)
    node.right = build(nums, mid + 1, end)

    node.total = node.left.total + node.right.total

    return node

👉 Interview Answer

To build a Segment Tree, I recursively split the array range in half.

If the range contains one element, I create a leaf node.

Otherwise, I build the left and right children, then combine their values to compute the current node value.

7️⃣ Range Query Operation

Purpose

query(node, left, right) returns the aggregate value inside:

[left, right]

Three Cases

Case 1: Full Cover

If node range is completely inside query range:

return node.total

Case 2: No Overlap

If node range does not overlap query range:

return 0

For sum query, neutral value is 0.

Case 3: Partial Overlap

Query both children and combine:

left_result + right_result

Code

def query(node, left, right):
    if node.end < left or node.start > right:
        return 0

    if left <= node.start and node.end <= right:
        return node.total

    return query(node.left, left, right) + query(node.right, left, right)

👉 Interview Answer

Segment Tree range query has three cases.

If the current node range is fully inside the query range, I return the node value directly.

If there is no overlap, I return the neutral value.

If there is partial overlap, I query both children and combine their results.

8️⃣ Point Update Operation

Purpose

Update changes one element:

nums[index] = value

Segment Tree must update all ranges that contain this index.

Code

def update(node, index, value):
    if node.start == node.end:
        node.total = value
        return

    mid = (node.start + node.end) // 2

    if index <= mid:
        update(node.left, index, value)
    else:
        update(node.right, index, value)

    node.total = node.left.total + node.right.total

Why O(log n)?

Each update follows one path from root to leaf.

Tree height is:

O(log n)

After changing the leaf, we recompute values on the path back up.

👉 Interview Answer

For a point update, I recursively go down to the leaf node representing the updated index.

After updating the leaf, I recompute every ancestor node on the path back to the root.

Since the tree height is O(log n), the update takes O(log n).

9️⃣ Complete Recursive Segment Tree Template

Range Sum Query Mutable

class SegmentTreeNode:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.total = 0
        self.left = None
        self.right = None


class NumArray:
    def __init__(self, nums):
        if not nums:
            self.root = None
        else:
            self.root = self.build(nums, 0, len(nums) - 1)

    def build(self, nums, start, end):
        node = SegmentTreeNode(start, end)

        if start == end:
            node.total = nums[start]
            return node

        mid = (start + end) // 2

        node.left = self.build(nums, start, mid)
        node.right = self.build(nums, mid + 1, end)

        node.total = node.left.total + node.right.total

        return node

    def update(self, index, val):
        self.update_tree(self.root, index, val)

    def update_tree(self, node, index, val):
        if node.start == node.end:
            node.total = val
            return

        mid = (node.start + node.end) // 2

        if index <= mid:
            self.update_tree(node.left, index, val)
        else:
            self.update_tree(node.right, index, val)

        node.total = node.left.total + node.right.total

    def sumRange(self, left, right):
        return self.query(self.root, left, right)

    def query(self, node, left, right):
        if node.end < left or node.start > right:
            return 0

        if left <= node.start and node.end <= right:
            return node.total

        return self.query(node.left, left, right) + self.query(node.right, left, right)

👉 Interview Answer

The recursive Segment Tree template has three core methods: build, update, and query.

Build recursively creates the tree. Update changes one leaf and recomputes ancestors. Query uses full overlap, no overlap, and partial overlap cases.

🔟 Complexity Analysis

Build

Every element becomes a leaf, and internal nodes combine children.

Time: O(n)
Space: O(n)

Query

Range query visits at most O(log n) relevant segments per level structure.

Time: O(log n)

Update

Point update follows one root-to-leaf path.

Time: O(log n)

Summary

Build:  O(n)
Query:  O(log n)
Update: O(log n)
Space:  O(n)

👉 Interview Answer

Segment Tree build takes O(n).

Range query takes O(log n), because it only visits a logarithmic number of relevant segments.

Point update also takes O(log n), because it updates one leaf and recomputes values along the root-to-leaf path.

Space complexity is O(n).

1️⃣1️⃣ Array-Based Segment Tree

Why Array-Based?

Instead of creating tree nodes, we can store the tree in an array.

This is common in competitive programming.

Size

A safe size is:

4 * n

Index Rules

For node index i:

left child  = 2 * i
right child = 2 * i + 1

If using zero-based tree array:

left child  = 2 * i + 1
right child = 2 * i + 2

Code

class SegmentTree:
    def __init__(self, nums):
        self.nums = nums
        self.n = len(nums)
        self.tree = [0] * (4 * self.n)

        if self.n > 0:
            self.build(1, 0, self.n - 1)

    def build(self, node, start, end):
        if start == end:
            self.tree[node] = self.nums[start]
            return

        mid = (start + end) // 2

        self.build(2 * node, start, mid)
        self.build(2 * node + 1, mid + 1, end)

        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

👉 Interview Answer

A Segment Tree can be implemented with an array instead of explicit tree nodes.

The tree array usually uses size 4n to safely store all nodes.

This avoids object overhead and is common in competitive programming.

1️⃣2️⃣ Array-Based Query

Code

def query(self, node, start, end, left, right):
    if end < left or start > right:
        return 0

    if left <= start and end <= right:
        return self.tree[node]

    mid = (start + end) // 2

    left_sum = self.query(2 * node, start, mid, left, right)
    right_sum = self.query(2 * node + 1, mid + 1, end, left, right)

    return left_sum + right_sum

Wrapper

def range_sum(self, left, right):
    return self.query(1, 0, self.n - 1, left, right)

👉 Interview Answer

Array-based query uses the same overlap logic as recursive node-based query.

If the current segment has no overlap, return neutral value.

If fully covered, return tree[node].

Otherwise, query both children and combine the result.

1️⃣3️⃣ Array-Based Update

Code

def update(self, node, start, end, index, value):
    if start == end:
        self.tree[node] = value
        return

    mid = (start + end) // 2

    if index <= mid:
        self.update(2 * node, start, mid, index, value)
    else:
        self.update(2 * node + 1, mid + 1, end, index, value)

    self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

Wrapper

def point_update(self, index, value):
    self.update(1, 0, self.n - 1, index, value)

👉 Interview Answer

Array-based update follows one path from root segment to leaf segment.

After updating the leaf value, I recompute parent nodes on the way back.

This is still O(log n).

1️⃣4️⃣ Complete Array-Based Segment Tree

class SegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (4 * self.n)

        if self.n > 0:
            self.build(nums, 1, 0, self.n - 1)

    def build(self, nums, node, start, end):
        if start == end:
            self.tree[node] = nums[start]
            return

        mid = (start + end) // 2

        self.build(nums, 2 * node, start, mid)
        self.build(nums, 2 * node + 1, mid + 1, end)

        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def query(self, node, start, end, left, right):
        if end < left or start > right:
            return 0

        if left <= start and end <= right:
            return self.tree[node]

        mid = (start + end) // 2

        left_sum = self.query(2 * node, start, mid, left, right)
        right_sum = self.query(2 * node + 1, mid + 1, end, left, right)

        return left_sum + right_sum

    def update(self, node, start, end, index, value):
        if start == end:
            self.tree[node] = value
            return

        mid = (start + end) // 2

        if index <= mid:
            self.update(2 * node, start, mid, index, value)
        else:
            self.update(2 * node + 1, mid + 1, end, index, value)

        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def range_sum(self, left, right):
        return self.query(1, 0, self.n - 1, left, right)

    def point_update(self, index, value):
        self.update(1, 0, self.n - 1, index, value)

👉 Interview Answer

The array-based Segment Tree stores tree nodes in a list.

Each recursive call knows the tree index and the segment range.

The logic is the same: build combines children, query handles overlap cases, and update recomputes ancestors.

1️⃣5️⃣ Iterative Segment Tree

Why Iterative?

Iterative Segment Tree is shorter and often faster.

It stores leaves in the second half of an array.

Layout

For array length n:

tree[n + i] = nums[i]

Parents are stored above:

tree[i] = tree[2 * i] + tree[2 * i + 1]

Code

class NumArray:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)

        for i in range(self.n):
            self.tree[self.n + i] = nums[i]

        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

👉 Interview Answer

Iterative Segment Tree stores leaves in the second half of the array.

Then it builds parent nodes from bottom to top.

This avoids recursion and is often simpler for range sum with point updates.

1️⃣6️⃣ Iterative Update

Code

def update(self, index, val):
    pos = index + self.n
    self.tree[pos] = val

    while pos > 1:
        pos //= 2
        self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]

Explanation

Update leaf:

tree[index + n] = value

Then move upward:

parent = pos // 2

Recompute parent using two children.

👉 Interview Answer

In iterative Segment Tree, point update first updates the leaf position.

Then I move upward to the root, recomputing each parent from its two children.

This takes O(log n).

1️⃣7️⃣ Iterative Range Query

Query Range

For inclusive query:

[left, right]

Convert to leaf positions:

left += n
right += n

Code

def sumRange(self, left, right):
    left += self.n
    right += self.n
    result = 0

    while left <= right:
        if left % 2 == 1:
            result += self.tree[left]
            left += 1

        if right % 2 == 0:
            result += self.tree[right]
            right -= 1

        left //= 2
        right //= 2

    return result

Intuition

If left is a right child, its segment is fully inside the query.

If right is a left child, its segment is fully inside the query.

Then move both pointers upward.

👉 Interview Answer

Iterative range query moves two pointers from the leaf level upward.

When the left pointer is a right child, that segment should be included.

When the right pointer is a left child, that segment should be included.

Then both pointers move to their parents until the range is fully processed.

1️⃣8️⃣ Complete Iterative Segment Tree Template

class NumArray:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)

        for i in range(self.n):
            self.tree[self.n + i] = nums[i]

        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def update(self, index, val):
        pos = index + self.n
        self.tree[pos] = val

        while pos > 1:
            pos //= 2
            self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]

    def sumRange(self, left, right):
        left += self.n
        right += self.n
        result = 0

        while left <= right:
            if left % 2 == 1:
                result += self.tree[left]
                left += 1

            if right % 2 == 0:
                result += self.tree[right]
                right -= 1

            left //= 2
            right //= 2

        return result

👉 Interview Answer

The iterative Segment Tree template is compact.

Leaves are stored at positions n through 2n - 1.

Update modifies a leaf and recomputes parents.

Query uses two pointers moving upward to collect fully covered segments.

1️⃣9️⃣ Range Minimum Query

Change the Aggregation

Segment Tree is not limited to sum.

For minimum query, each node stores:

minimum value in its range

Neutral Value

For no overlap, return:

infinity

Code

class MinSegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [float("inf")] * (4 * self.n)

        if self.n > 0:
            self.build(nums, 1, 0, self.n - 1)

    def build(self, nums, node, start, end):
        if start == end:
            self.tree[node] = nums[start]
            return

        mid = (start + end) // 2

        self.build(nums, 2 * node, start, mid)
        self.build(nums, 2 * node + 1, mid + 1, end)

        self.tree[node] = min(self.tree[2 * node], self.tree[2 * node + 1])

    def query_min(self, node, start, end, left, right):
        if end < left or start > right:
            return float("inf")

        if left <= start and end <= right:
            return self.tree[node]

        mid = (start + end) // 2

        return min(
            self.query_min(2 * node, start, mid, left, right),
            self.query_min(2 * node + 1, mid + 1, end, left, right)
        )

👉 Interview Answer

Segment Tree can support different aggregation functions.

For range minimum query, each node stores the minimum value in its segment.

The query logic stays the same, but the combine operation becomes min, and the no-overlap neutral value becomes infinity.

2️⃣0️⃣ Range Maximum Query

Change the Aggregation

For maximum query, each node stores:

maximum value in its range

Neutral Value

For no overlap:

negative infinity

Query Logic

return max(left_result, right_result)

👉 Interview Answer

For range maximum query, Segment Tree stores the max value for each segment.

The structure is the same as range sum.

Only the combine function changes from addition to max, and the neutral value changes to negative infinity.

2️⃣1️⃣ Segment Tree vs Binary Indexed Tree

Binary Indexed Tree

Good for:

prefix sum
range sum
point update
less code
less memory

Segment Tree

Good for:

range sum
range min
range max
custom aggregation
more flexible queries
lazy propagation

Comparison

Pattern	Best For
Binary Indexed Tree	Prefix/range sum with point updates
Segment Tree	More general range queries
Segment Tree	Min/max/custom aggregation
Fenwick Tree	Simpler sum-only problems

👉 Interview Answer

Binary Indexed Tree is simpler and more memory-efficient for prefix sum or range sum with point updates.

Segment Tree is more flexible.

It can support sum, min, max, and more complex range aggregations.

If the problem only needs sum, Fenwick Tree may be easier. If the problem needs flexible range aggregation, Segment Tree is usually better.

2️⃣2️⃣ Segment Tree vs Prefix Sum

Prefix Sum

Good for:

static array
many range sum queries
no updates

Segment Tree

Good for:

dynamic array
updates and queries mixed
range min / max
custom aggregation

Comparison

Pattern	Query	Update	Best For
Prefix Sum	O(1)	O(n)	Static range sum
Segment Tree	O(log n)	O(log n)	Mutable range queries

👉 Interview Answer

Prefix sum is better for static range sum queries because query is O(1).

Segment Tree is better when updates are mixed with range queries.

Segment Tree gives O(log n) query and O(log n) update, which is much better than rebuilding prefix sums after every update.

2️⃣3️⃣ Lazy Propagation

Problem

Sometimes we need range updates:

add value to every element from left to right

Without lazy propagation, updating every element costs:

O(n)

Lazy Idea

Instead of immediately updating all child nodes, store a pending update at the current node.

lazy[node] = pending value

Push it down only when needed.

Common Use Cases

range add
range assign
range sum query
range min query
range max query

👉 Interview Answer

Lazy propagation is an optimization for range updates.

Instead of immediately updating every element in a range, we store a pending update on a Segment Tree node.

That pending value is pushed to children only when necessary.

This allows range updates and range queries to stay O(log n).

2️⃣4️⃣ Common Edge Cases

Empty Array

nums = []

Need to avoid building invalid tree.

Single Element

nums = [5]

Root is also a leaf.

Query Entire Range

query(0, n - 1)

Should return root value.

Query One Element

query(i, i)

Should return that element.

Invalid Range

Some problems may avoid this, but in real code:

left > right

should be handled or rejected.

👉 Interview Answer

Common Segment Tree edge cases include empty arrays, single-element arrays, querying the entire range, querying a single element, and invalid query ranges.

I make sure the build function handles empty input, and that query boundaries are inclusive and consistent.

2️⃣5️⃣ Common Mistakes

Mistake 1: Wrong Mid Split

Use:

mid = (start + end) // 2

Left:

[start, mid]

Right:

[mid + 1, end]

Mistake 2: Infinite Recursion

Wrong split can cause:

[start, mid]
[mid, end]

This may never shrink.

Mistake 3: Forgetting to Recompute Parent

After update:

tree[node] = tree[left_child] + tree[right_child]

Mistake 4: Wrong Neutral Value

For sum:

For min:

infinity

For max:

negative infinity

Mistake 5: Confusing Inclusive and Exclusive Ranges

Most LeetCode Segment Tree problems use:

[left, right]

inclusive ranges.

Mistake 6: Using Prefix Sum When Updates Exist

Prefix sum update can be O(n).

Segment Tree is better for frequent updates.

👉 Interview Answer

Common Segment Tree mistakes include wrong mid split, infinite recursion, forgetting to recompute parent values after update, using the wrong neutral value, mixing inclusive and exclusive ranges, and using prefix sum when frequent updates are required.

2️⃣6️⃣ When Segment Tree Applies

Good Fit

Use Segment Tree when the problem asks for:

range query
point update
range sum mutable
range min mutable
range max mutable
dynamic array query
many updates and many queries
custom interval aggregation

Problem Signals

Look for words like:

range
query
update
mutable
sumRange
minimum in range
maximum in range
interval
many operations

👉 Interview Answer

I consider Segment Tree when the problem involves repeated range queries and updates.

Common signals include range sum query mutable, range min or max query, point updates, and many mixed query/update operations.

If the array is static, prefix sum may be simpler. If the array is dynamic, Segment Tree is often the right choice.

2️⃣7️⃣ When Segment Tree Does Not Apply

Not Good Fit

Segment Tree may not be ideal when:

array is static
only exact lookup is needed
only prefix sum is needed and Fenwick Tree is simpler
input size is small
no repeated range queries

Better Alternatives

Problem Type	Better Pattern
Static range sum	Prefix Sum
Prefix sum with point update	Fenwick Tree
Exact lookup	HashMap / Array
Small input	Brute Force
Range query without updates	Sparse Table / Prefix Sum
Monotonic nearest greater/smaller	Monotonic Stack

👉 Interview Answer

Segment Tree is powerful but not always necessary.

For static range sum, prefix sum is simpler and faster.

For sum-only point updates, Fenwick Tree may be simpler.

Segment Tree is most useful when range queries and updates are both frequent, or when the aggregation is more flexible than simple sum.

2️⃣8️⃣ Standard Templates

Recursive Node-Based Template

class SegmentTreeNode:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.total = 0
        self.left = None
        self.right = None

Recursive Array-Based Template

class SegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (4 * self.n)

        if self.n > 0:
            self.build(nums, 1, 0, self.n - 1)

Iterative Template

class NumArray:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)

        for i in range(self.n):
            self.tree[self.n + i] = nums[i]

        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

Generic Combine Idea

node.value = combine(left.value, right.value)

Examples:

sum: left + right
min: min(left, right)
max: max(left, right)
gcd: gcd(left, right)

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

A Segment Tree is a tree data structure used for efficient range queries and updates.

Each node represents a segment of the original array. A leaf node represents one element. An internal node stores aggregated information from its left and right children.

For example, in a range sum Segment Tree, each node stores the sum of its segment. For range minimum query, each node stores the minimum value in its segment. For range maximum query, each node stores the maximum value.

Segment Tree is useful when the array is mutable. Prefix sum can answer static range sum queries in O(1), but updates are expensive because many prefix values may need to change. Segment Tree supports both range query and point update in O(log n).

Build recursively splits the array into halves. If the segment has one element, we create a leaf. Otherwise, we build the left and right children, then combine their values to compute the current node.

Range query has three cases. If the current segment is fully inside the query range, return the node value. If it has no overlap, return the neutral value. If it partially overlaps, query both children and combine their results.

Point update follows one path from root to leaf. After updating the leaf, we recompute all ancestors on the path back to the root.

The time complexity is: build O(n), query O(log n), update O(log n), and space O(n).

Segment Tree can be implemented recursively with explicit nodes, recursively with an array of size 4n, or iteratively with an array of size 2n.

Compared with Fenwick Tree, Segment Tree is more flexible. Fenwick Tree is simpler for prefix sum and range sum, but Segment Tree can handle sum, min, max, gcd, and more complex aggregation logic.

For range updates, Segment Tree can be extended with lazy propagation. Lazy propagation stores pending updates on nodes and pushes them to children only when needed.

At a senior level, I would explain: what each node represents, what aggregate value is stored, how build combines children, how query handles overlap cases, how update recomputes ancestors, why it is better than prefix sum for mutable arrays, and when Fenwick Tree or prefix sum might be simpler.

⭐ Final Insight

Segment Tree 的核心不是“背模板”。

它的核心是把 array 拆成 hierarchical segments，并在每个 segment 上存一个 aggregate value。

Senior-level 的重点是：

node 代表什么 range， node 存什么 aggregate， combine function 是什么， query 的 full overlap / no overlap / partial overlap 如何处理， update 为什么只影响 root-to-leaf path，为什么 prefix sum 不适合 frequent updates，以及什么时候 Fenwick Tree 更简单。

能讲清楚这些， Segment Tree 就是一种处理 mutable range query 的核心数据结构。

中文部分

🎯 Segment Tree

1️⃣ 核心框架

讨论 Segment Tree 时，我通常从：

Segment Tree 解决什么问题
Range query problem
为什么 prefix sum 不够
Segment tree structure
Build operation
Query operation
Update operation
Recursive implementation
Iterative implementation
高级工程师解释方式

2️⃣ 要解决什么问题？

Segment Tree 用来高效处理 range queries，同时支持 updates。

它常用于：

Range sum query
Range minimum query
Range maximum query
Dynamic array updates
Mutable prefix-style queries
Count queries over ranges
Interval aggregation
Range frequency problems
Lazy propagation problems
Competitive programming range query problems

核心思想是：

把 array 拆成很多 segments。
每个 node 存一个 segment 的信息。
Range query 通过组合相关 segments 得到答案。
Update 只更新受影响的 segments。

👉 面试回答

Segment Tree 是一种用于高效处理 range queries 和 point updates 的 tree data structure。

每个 node 代表 array 中的一个 range。

node 中存这个 range 的 aggregate information，比如 sum、min 或 max。

当 array 会变化，同时还需要快速查询 range 信息时， Segment Tree 很有用。

3️⃣ 为什么 Segment Tree 有效？

Range Query Problem

假设有：

nums = [2, 4, 5, 7, 8, 9]

我们想查询：

index 1 到 4 的 sum

也就是：

4 + 5 + 7 + 8 = 24

Brute force 每次都扫描 range。

Time: O(n)

Segment Tree Idea

Segment Tree 会预先存储很多 range 的信息。

Example:

[0, 5]
├── [0, 2]
│   ├── [0, 1]
│   └── [2, 2]
└── [3, 5]
    ├── [3, 4]
    └── [5, 5]

每个 node 存自己 range 的 sum。

👉 面试回答

Segment Tree 通过递归地把 array range 切成更小的 ranges 来工作。

每个 tree node 存一个 range 的答案。

Range query 时，不需要扫描每个 element，只需要组合完全覆盖 query range 的若干 tree nodes。

4️⃣ 为什么 Prefix Sum 不够？

Prefix Sum 适合 Static Array

对于 static array：

range_sum(left, right) = prefix[right + 1] - prefix[left]

Query 是：

O(1)

Update 的问题

如果一个值改变：

nums[i] = new_value

那么 index i 后面的很多 prefix values 都要更新。

Update 变成：

O(n)

Segment Tree Tradeoff

Segment Tree 提供：

Query: O(log n)
Update: O(log n)

当 queries 和 updates 都很多时，这个 tradeoff 更合适。

👉 面试回答

Prefix sum 很适合 static array。

但如果 array 会被更新，一次 update 可能导致很多 prefix values 都要变化。

Segment Tree 适合同时需要 efficient range queries 和 efficient updates 的场景。

它把 query 和 update 都控制在 O(log n)。

5️⃣ Segment Tree Structure

Basic Idea

每个 node 代表一个 range：

[start, end]

对于 range sum，每个 node 存：

nums[start:end + 1] 的 sum

Leaf Node

Leaf node 代表一个单独 element：

[start == end]

Example:

[3, 3]

存储：

nums[3]

Internal Node

Internal node 由 children 合并而来：

node.sum = left_child.sum + right_child.sum

👉 面试回答

Segment Tree 中，每个 node 代表 array 的一个 range。

Leaf node 代表一个单独元素。

Internal node 存 left child 和 right child 的 combined result。

对 range sum 来说， combine operation 就是 addition。

6️⃣ Build Operation

Purpose

Build 用 input array 创建 Segment Tree。

Steps:

如果 start == end:
    创建 leaf node

否则:
    把 range 分成两半
    build left child
    build right child
    combine children

Code

class SegmentTreeNode:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.total = 0
        self.left = None
        self.right = None


def build(nums, start, end):
    if start == end:
        node = SegmentTreeNode(start, end)
        node.total = nums[start]
        return node

    mid = (start + end) // 2

    node = SegmentTreeNode(start, end)
    node.left = build(nums, start, mid)
    node.right = build(nums, mid + 1, end)

    node.total = node.left.total + node.right.total

    return node

👉 面试回答

Build Segment Tree 时，我会递归地把 array range 切成两半。

如果当前 range 只有一个元素，就创建 leaf node。

否则，先 build left 和 right children，再 combine 它们的值来得到当前 node 的值。

7️⃣ Range Query Operation

Purpose

query(node, left, right) 返回：

[left, right]

范围内的 aggregate value。

Three Cases

Case 1: Full Cover

如果当前 node range 完全在 query range 内：

return node.total

Case 2: No Overlap

如果当前 node range 和 query range 没有交集：

return 0

对 sum query 来说， neutral value 是 0。

Case 3: Partial Overlap

查询左右 children 并合并：

left_result + right_result

Code

def query(node, left, right):
    if node.end < left or node.start > right:
        return 0

    if left <= node.start and node.end <= right:
        return node.total

    return query(node.left, left, right) + query(node.right, left, right)

👉 面试回答

Segment Tree range query 有三种情况。

如果当前 node range 被 query range 完全覆盖，直接返回 node value。

如果完全没有 overlap，返回 neutral value。

如果部分 overlap，就查询左右 children，并 combine 它们的结果。

8️⃣ Point Update Operation

Purpose

Update 改变一个元素：

nums[index] = value

Segment Tree 需要更新所有包含这个 index 的 ranges。

Code

def update(node, index, value):
    if node.start == node.end:
        node.total = value
        return

    mid = (node.start + node.end) // 2

    if index <= mid:
        update(node.left, index, value)
    else:
        update(node.right, index, value)

    node.total = node.left.total + node.right.total

Why O(log n)?

每次 update 只沿着 root 到 leaf 的一条路径走。

Tree height 是：

O(log n)

修改 leaf 后，再一路向上 recompute ancestor values。

👉 面试回答

Point update 时，我会递归走到代表 index 的 leaf node。

修改 leaf 之后，再一路向上重新计算所有 ancestor nodes。

因为 tree height 是 O(log n)，所以 update 是 O(log n)。

9️⃣ 完整 Recursive Segment Tree Template

Range Sum Query Mutable

class SegmentTreeNode:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.total = 0
        self.left = None
        self.right = None


class NumArray:
    def __init__(self, nums):
        if not nums:
            self.root = None
        else:
            self.root = self.build(nums, 0, len(nums) - 1)

    def build(self, nums, start, end):
        node = SegmentTreeNode(start, end)

        if start == end:
            node.total = nums[start]
            return node

        mid = (start + end) // 2

        node.left = self.build(nums, start, mid)
        node.right = self.build(nums, mid + 1, end)

        node.total = node.left.total + node.right.total

        return node

    def update(self, index, val):
        self.update_tree(self.root, index, val)

    def update_tree(self, node, index, val):
        if node.start == node.end:
            node.total = val
            return

        mid = (node.start + node.end) // 2

        if index <= mid:
            self.update_tree(node.left, index, val)
        else:
            self.update_tree(node.right, index, val)

        node.total = node.left.total + node.right.total

    def sumRange(self, left, right):
        return self.query(self.root, left, right)

    def query(self, node, left, right):
        if node.end < left or node.start > right:
            return 0

        if left <= node.start and node.end <= right:
            return node.total

        return self.query(node.left, left, right) + self.query(node.right, left, right)

👉 面试回答

Recursive Segment Tree 模板有三个核心方法： build、update 和 query。

Build 递归创建 tree。 Update 修改一个 leaf 并重新计算 ancestors。 Query 使用 full overlap、no overlap 和 partial overlap 三种情况。

🔟 Complexity Analysis

Build

每个元素成为一个 leaf， internal nodes 由 children 合并而来。

Time: O(n)
Space: O(n)

Query

Range query 只访问有限数量的相关 segments。

Time: O(log n)

Update

Point update 只走一条 root-to-leaf path。

Time: O(log n)

Summary

Build:  O(n)
Query:  O(log n)
Update: O(log n)
Space:  O(n)

👉 面试回答

Segment Tree build 是 O(n)。

Range query 是 O(log n)，因为它只访问和 query range 相关的少量 segments。

Point update 也是 O(log n)，因为它只更新一个 leaf，并重新计算 root-to-leaf path 上的 nodes。

Space complexity 是 O(n)。

1️⃣1️⃣ Array-Based Segment Tree

Why Array-Based?

除了创建 tree nodes，也可以用 array 存 Segment Tree。

这在 competitive programming 中很常见。

Size

安全大小通常是：

4 * n

Index Rules

如果 node index 是 i：

left child  = 2 * i
right child = 2 * i + 1

如果使用 zero-based tree array：

left child  = 2 * i + 1
right child = 2 * i + 2

Code

class SegmentTree:
    def __init__(self, nums):
        self.nums = nums
        self.n = len(nums)
        self.tree = [0] * (4 * self.n)

        if self.n > 0:
            self.build(1, 0, self.n - 1)

    def build(self, node, start, end):
        if start == end:
            self.tree[node] = self.nums[start]
            return

        mid = (start + end) // 2

        self.build(2 * node, start, mid)
        self.build(2 * node + 1, mid + 1, end)

        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

👉 面试回答

Segment Tree 可以用 array 实现，不一定要显式创建 tree nodes。

tree array 通常开 4n 大小，可以安全存下所有 nodes。

这种方式减少 object overhead，在竞赛和面试中都很常见。

1️⃣2️⃣ Array-Based Query

Code

def query(self, node, start, end, left, right):
    if end < left or start > right:
        return 0

    if left <= start and end <= right:
        return self.tree[node]

    mid = (start + end) // 2

    left_sum = self.query(2 * node, start, mid, left, right)
    right_sum = self.query(2 * node + 1, mid + 1, end, left, right)

    return left_sum + right_sum

Wrapper

def range_sum(self, left, right):
    return self.query(1, 0, self.n - 1, left, right)

👉 面试回答

Array-based query 和 node-based query 使用同样的 overlap 逻辑。

如果当前 segment 没有 overlap，返回 neutral value。

如果完全被 query range 覆盖，返回 tree[node]。

否则查询左右 children 并合并结果。

1️⃣3️⃣ Array-Based Update

Code

def update(self, node, start, end, index, value):
    if start == end:
        self.tree[node] = value
        return

    mid = (start + end) // 2

    if index <= mid:
        self.update(2 * node, start, mid, index, value)
    else:
        self.update(2 * node + 1, mid + 1, end, index, value)

    self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

Wrapper

def point_update(self, index, value):
    self.update(1, 0, self.n - 1, index, value)

👉 面试回答

Array-based update 会从 root segment 走到 leaf segment。

修改 leaf 后，再一路向上 recompute parent nodes。

时间复杂度仍然是 O(log n)。

1️⃣4️⃣ 完整 Array-Based Segment Tree

class SegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (4 * self.n)

        if self.n > 0:
            self.build(nums, 1, 0, self.n - 1)

    def build(self, nums, node, start, end):
        if start == end:
            self.tree[node] = nums[start]
            return

        mid = (start + end) // 2

        self.build(nums, 2 * node, start, mid)
        self.build(nums, 2 * node + 1, mid + 1, end)

        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def query(self, node, start, end, left, right):
        if end < left or start > right:
            return 0

        if left <= start and end <= right:
            return self.tree[node]

        mid = (start + end) // 2

        left_sum = self.query(2 * node, start, mid, left, right)
        right_sum = self.query(2 * node + 1, mid + 1, end, left, right)

        return left_sum + right_sum

    def update(self, node, start, end, index, value):
        if start == end:
            self.tree[node] = value
            return

        mid = (start + end) // 2

        if index <= mid:
            self.update(2 * node, start, mid, index, value)
        else:
            self.update(2 * node + 1, mid + 1, end, index, value)

        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def range_sum(self, left, right):
        return self.query(1, 0, self.n - 1, left, right)

    def point_update(self, index, value):
        self.update(1, 0, self.n - 1, index, value)

👉 面试回答

Array-based Segment Tree 把 tree nodes 存在 list 中。

每次 recursive call 都知道当前 tree index 和 segment range。

核心逻辑不变： build combine children， query 处理 overlap cases， update recompute ancestors。

1️⃣5️⃣ Iterative Segment Tree

Why Iterative?

Iterative Segment Tree 通常更短，也避免了 recursion。

它把 leaves 放在 array 的后半部分。

Layout

如果 array 长度是 n：

tree[n + i] = nums[i]

Parent 存在上层：

tree[i] = tree[2 * i] + tree[2 * i + 1]

Code

class NumArray:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)

        for i in range(self.n):
            self.tree[self.n + i] = nums[i]

        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

👉 面试回答

Iterative Segment Tree 会把 leaves 存在 array 的第二半。

然后从 bottom to top 构建 parent nodes。

这种写法不需要 recursion，对 range sum with point updates 很简洁。

1️⃣6️⃣ Iterative Update

Code

def update(self, index, val):
    pos = index + self.n
    self.tree[pos] = val

    while pos > 1:
        pos //= 2
        self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]

Explanation

先更新 leaf：

tree[index + n] = value

然后向上移动：

parent = pos // 2

用两个 children 重新计算 parent。

👉 面试回答

Iterative Segment Tree 中， point update 先修改 leaf position。

然后一路向上移动到 root，重新计算每个 parent。

时间复杂度是 O(log n)。

1️⃣7️⃣ Iterative Range Query

Query Range

对于 inclusive query：

[left, right]

先转成 leaf positions：

left += n
right += n

Code

def sumRange(self, left, right):
    left += self.n
    right += self.n
    result = 0

    while left <= right:
        if left % 2 == 1:
            result += self.tree[left]
            left += 1

        if right % 2 == 0:
            result += self.tree[right]
            right -= 1

        left //= 2
        right //= 2

    return result

Intuition

如果 left 是 right child，它代表的 segment 完全在 query range 中。

如果 right 是 left child，它代表的 segment 完全在 query range 中。

然后两个 pointers 向上移动。

👉 面试回答

Iterative range query 用两个 pointers 从 leaf level 向上移动。

当 left pointer 是 right child 时，当前 segment 应该被加入结果。

当 right pointer 是 left child 时，当前 segment 也应该被加入结果。

然后两个 pointers 移动到 parent，直到整个 range 被处理完。

1️⃣8️⃣ 完整 Iterative Segment Tree Template

class NumArray:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)

        for i in range(self.n):
            self.tree[self.n + i] = nums[i]

        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def update(self, index, val):
        pos = index + self.n
        self.tree[pos] = val

        while pos > 1:
            pos //= 2
            self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]

    def sumRange(self, left, right):
        left += self.n
        right += self.n
        result = 0

        while left <= right:
            if left % 2 == 1:
                result += self.tree[left]
                left += 1

            if right % 2 == 0:
                result += self.tree[right]
                right -= 1

            left //= 2
            right //= 2

        return result

👉 面试回答

Iterative Segment Tree 模板非常 compact。

Leaves 存在 n 到 2n - 1 的位置。

Update 修改一个 leaf 并向上 recompute parents。

Query 用两个 pointers 向上移动，收集完全被覆盖的 segments。

1️⃣9️⃣ Range Minimum Query

Change the Aggregation

Segment Tree 不只支持 sum。

对于 minimum query，每个 node 存：

当前 range 的 minimum value

Neutral Value

对于 no overlap，返回：

infinity

Code

class MinSegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [float("inf")] * (4 * self.n)

        if self.n > 0:
            self.build(nums, 1, 0, self.n - 1)

    def build(self, nums, node, start, end):
        if start == end:
            self.tree[node] = nums[start]
            return

        mid = (start + end) // 2

        self.build(nums, 2 * node, start, mid)
        self.build(nums, 2 * node + 1, mid + 1, end)

        self.tree[node] = min(self.tree[2 * node], self.tree[2 * node + 1])

    def query_min(self, node, start, end, left, right):
        if end < left or start > right:
            return float("inf")

        if left <= start and end <= right:
            return self.tree[node]

        mid = (start + end) // 2

        return min(
            self.query_min(2 * node, start, mid, left, right),
            self.query_min(2 * node + 1, mid + 1, end, left, right)
        )

👉 面试回答

Segment Tree 可以支持不同的 aggregation function。

对 range minimum query，每个 node 存当前 segment 的 minimum value。

Query 逻辑不变，只是 combine operation 变成 min， no-overlap 的 neutral value 变成 infinity。

2️⃣0️⃣ Range Maximum Query

Change the Aggregation

对于 maximum query，每个 node 存：

当前 range 的 maximum value

Neutral Value

对于 no overlap：

negative infinity

Query Logic

return max(left_result, right_result)

👉 面试回答

对 range maximum query， Segment Tree 存每个 segment 的 max value。

结构和 range sum 一样。

只是 combine function 从 addition 变成 max， neutral value 变成 negative infinity。

2️⃣1️⃣ Segment Tree vs Binary Indexed Tree

Binary Indexed Tree

适合：

prefix sum
range sum
point update
less code
less memory

Segment Tree

适合：

range sum
range min
range max
custom aggregation
more flexible queries
lazy propagation

Comparison

Pattern	Best For
Binary Indexed Tree	Prefix/range sum with point updates
Segment Tree	More general range queries
Segment Tree	Min/max/custom aggregation
Fenwick Tree	Simpler sum-only problems

👉 面试回答

Binary Indexed Tree 对 prefix sum 或 range sum with point updates 来说更简单，也更省内存。

Segment Tree 更灵活。

它可以支持 sum、min、max，以及更复杂的 range aggregation。

如果题目只需要 sum， Fenwick Tree 可能更简单。

如果题目需要更灵活的 range aggregation， Segment Tree 通常更合适。

2️⃣2️⃣ Segment Tree vs Prefix Sum

Prefix Sum

适合：

static array
many range sum queries
no updates

Segment Tree

适合：

dynamic array
updates and queries mixed
range min / max
custom aggregation

Comparison

Pattern	Query	Update	Best For
Prefix Sum	O(1)	O(n)	Static range sum
Segment Tree	O(log n)	O(log n)	Mutable range queries

👉 面试回答

Prefix sum 更适合 static range sum queries，因为 query 是 O(1)。

Segment Tree 更适合 updates 和 range queries 混合出现的场景。

Segment Tree 的 query 和 update 都是 O(log n)，比每次 update 后重建 prefix sum 更合适。

2️⃣3️⃣ Lazy Propagation

Problem

有时我们需要 range updates：

给 left 到 right 的每个元素都加上一个 value

如果不用 lazy propagation，逐个元素 update 是：

O(n)

Lazy Idea

不要立刻更新所有 child nodes。

而是在当前 node 上存一个 pending update。

lazy[node] = pending value

等真正需要访问 children 时再 push down。

Common Use Cases

range add
range assign
range sum query
range min query
range max query

👉 面试回答

Lazy propagation 是 Segment Tree 处理 range updates 的优化。

它不会立刻更新 range 内的每个元素。

而是把 pending update 存在当前 Segment Tree node 上。

当之后需要访问 children 时，再把 lazy value push down。

这样 range update 和 range query 都可以保持 O(log n)。

2️⃣4️⃣ 常见 Edge Cases

Empty Array

nums = []

需要避免 build invalid tree。

Single Element

nums = [5]

Root 同时也是 leaf。

Query Entire Range

query(0, n - 1)

应该返回 root value。

Query One Element

query(i, i)

应该返回该元素。

Invalid Range

部分题目不会出现，但真实代码中：

left > right

需要处理或拒绝。

👉 面试回答

Segment Tree 常见 edge cases 包括 empty array、 single-element array、 query entire range、 query single element，以及 invalid query range。

我会确保 build 能处理 empty input，并且 query boundaries 始终保持 inclusive 一致。

2️⃣5️⃣ 常见错误

Mistake 1: Mid Split 写错

使用：

mid = (start + end) // 2

Left:

[start, mid]

Right:

[mid + 1, end]

Mistake 2: Infinite Recursion

错误 split 可能导致：

[start, mid]
[mid, end]

range 没有缩小，造成 infinite recursion。

Mistake 3: Update 后忘记 Recompute Parent

Update 后需要：

tree[node] = tree[left_child] + tree[right_child]

Mistake 4: Neutral Value 写错

对于 sum：

对于 min：

infinity

对于 max：

negative infinity

Mistake 5: 混淆 Inclusive 和 Exclusive Ranges

多数 LeetCode Segment Tree 问题使用：

[left, right]

inclusive ranges。

Mistake 6: 有 Updates 还用 Prefix Sum

Prefix sum 在有 frequent updates 时， update 可能是 O(n)。

Segment Tree 更适合 frequent updates。

👉 面试回答

Segment Tree 常见错误包括： mid split 写错、 infinite recursion、 update 后忘记 recompute parent value、使用错误 neutral value、混淆 inclusive 和 exclusive ranges，以及在 frequent updates 场景下错误使用 prefix sum。

2️⃣6️⃣ 什么时候 Segment Tree 适用？

Good Fit

当题目问：

range query
point update
range sum mutable
range min mutable
range max mutable
dynamic array query
many updates and many queries
custom interval aggregation

Problem Signals

看到这些关键词想到 Segment Tree：

range
query
update
mutable
sumRange
minimum in range
maximum in range
interval
many operations

👉 面试回答

当问题涉及 repeated range queries 和 updates 时，我会考虑 Segment Tree。

常见信号包括 range sum query mutable、 range min 或 max query、 point updates，以及大量 query/update 混合操作。

如果 array 是 static， prefix sum 可能更简单。

如果 array 是 dynamic， Segment Tree 通常更合适。

2️⃣7️⃣ 什么时候 Segment Tree 不适用？

Not Good Fit

Segment Tree 不一定适合：

array is static
only exact lookup is needed
only prefix sum is needed and Fenwick Tree is simpler
input size is small
no repeated range queries

Better Alternatives

Problem Type	Better Pattern
Static range sum	Prefix Sum
Prefix sum with point update	Fenwick Tree
Exact lookup	HashMap / Array
Small input	Brute Force
Range query without updates	Sparse Table / Prefix Sum
Monotonic nearest greater/smaller	Monotonic Stack

👉 面试回答

Segment Tree 很强大，但不是所有 range 问题都需要用。

对 static range sum， prefix sum 更简单也更快。

对 sum-only point updates， Fenwick Tree 可能更简单。

Segment Tree 最适合 frequent range queries 和 updates，或 aggregation 不只是简单 prefix sum 的情况。

2️⃣8️⃣ 标准模板

Recursive Node-Based Template

class SegmentTreeNode:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.total = 0
        self.left = None
        self.right = None

Recursive Array-Based Template

class SegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (4 * self.n)

        if self.n > 0:
            self.build(nums, 1, 0, self.n - 1)

Iterative Template

class NumArray:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)

        for i in range(self.n):
            self.tree[self.n + i] = nums[i]

        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

Generic Combine Idea

node.value = combine(left.value, right.value)

Examples:

sum: left + right
min: min(left, right)
max: max(left, right)
gcd: gcd(left, right)

🧠 Staff-Level Answer Final

👉 面试回答完整版本

Segment Tree 是一种用于高效处理 range queries 和 updates 的 tree data structure。

每个 node 代表原数组中的一个 segment。 Leaf node 代表一个单独元素。 Internal node 存储 left child 和 right child 的 aggregate result。

例如，在 range sum Segment Tree 中，每个 node 存当前 segment 的 sum。在 range minimum query 中，每个 node 存当前 segment 的 minimum value。在 range maximum query 中，每个 node 存 maximum value。

Segment Tree 适合 mutable array。 Prefix sum 可以在 static array 中用 O(1) 回答 range sum query，但是 update 很贵，因为很多 prefix values 可能都要变化。 Segment Tree 可以同时支持 O(log n) range query 和 O(log n) point update。

Build 的过程是递归地把 array range 分成两半。如果 segment 只有一个元素，就创建 leaf。否则， build left child 和 right child，然后 combine 它们的值来得到当前 node。

Range query 有三种情况。如果当前 segment 完全在 query range 中，直接返回 node value。如果没有 overlap，返回 neutral value。如果部分 overlap，查询左右 children 并 combine 结果。

Point update 会沿着 root 到 leaf 的一条路径走。修改 leaf 后，一路向上 recompute ancestors。

时间复杂度是： build O(n)， query O(log n)， update O(log n)， space O(n)。

Segment Tree 可以用 explicit nodes 递归实现，也可以用 4n array 递归实现，还可以用 2n array 做 iterative implementation。

和 Fenwick Tree 相比， Segment Tree 更灵活。 Fenwick Tree 对 prefix sum 和 range sum 更简单，但 Segment Tree 可以处理 sum、min、max、gcd，以及更复杂的 aggregation logic。

对于 range updates， Segment Tree 可以扩展 lazy propagation。 Lazy propagation 会把 pending updates 存在 node 上，在需要时再 push 到 children。

高级工程师解释 Segment Tree 时，我会讲清楚：每个 node 代表什么 range，存什么 aggregate value， build 如何 combine children， query 如何处理 overlap cases， update 如何 recompute ancestors，为什么它比 prefix sum 更适合 mutable arrays，以及什么时候 Fenwick Tree 或 prefix sum 更简单。

⭐ Final Insight

Segment Tree 的核心不是“背模板”。

它的核心是把 array 拆成 hierarchical segments，并在每个 segment 上存一个 aggregate value。

Senior-level 的重点是：

node 代表什么 range， node 存什么 aggregate， combine function 是什么， query 的 full overlap / no overlap / partial overlap 如何处理， update 为什么只影响 root-to-leaf path，为什么 prefix sum 不适合 frequent updates，以及什么时候 Fenwick Tree 更简单。

能讲清楚这些， Segment Tree 就是一种处理 mutable range query 的核心数据结构。