Segment Tree Implementation

The segment tree structure is also used to solve interval query problems while supporting dynamic updates of elements, addressing the limitations of the prefix sum technique. However, the trade-off is a slightly higher time complexity, with both interval query and single-point update operations having a time complexity of $O(\log n)$.

The principles of segment trees have already been explained in the previous data structure basics chapter Core Principles and Visualization of Segment Trees. This article will not repeat them and will directly provide the code implementation of segment trees.

Linked Implementation vs. Array Implementation

The most straightforward idea is to implement a segment tree using a SegmentNode class similar to a binary tree node. We can refer to this as the linked implementation of a segment tree:

// Segment Tree Node
class SegmentNode {
    int start, end;
    int mergeValue;
    // Left and right child nodes
    SegmentNode left = null, right = null;

    public SegmentNode(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

// Segment Tree
class SegmentTree {
    SegmentNode root;

    // ...
}

Since a segment tree is a structure that is nearly a complete binary tree, it can also be stored using an array. There is no need to actually use SegmentNode to construct the tree structure. We might call this implementation the array-based implementation of the segment tree:

// Segment Tree
class SegmentTree {
    int[] tree;

    // ...
}

From the perspective of algorithm analysis, the theoretical complexity of both implementations is the same. However, the linked structure requires additional maintenance of pointer information, so in practical execution, it is certainly less efficient than the array implementation. Implementing a tree structure on an array is more abstract and harder to understand.

This site will provide code for both implementations. We will first explain the linked implementation; once you understand it, looking at the array implementation will be easier.

In actual written exams, if a segment tree is needed, you can directly copy the code of the array implementation for use.