Lazy Update Segment Tree Implementation

In Basic Implementation of Segment Tree, segment trees are implemented using arrays and linked lists, with two optimization points left at the end: interval update issues and memory optimization for sparse data.

Optimization: Dynamic Segment Tree addresses the memory optimization issue for sparse data. Based on the linked implementation of DynamicSegmentTree, this article introduces the rangeAdd/rangeUpdate methods using "lazy update" technology, completing arbitrary length interval updates in $O(\log N)$ time complexity.

The interval update segment tree implemented in this article differs from the previous single point update segment tree in several ways:

1. Since a single point update can be regarded as an interval update of length 1 with a complexity of $O(\log N)$, we no longer need to implement single point updates separately.

2. We do not accept merge aggregation functions due to interval lazy updates. Considering different aggregation functions simultaneously introduces some programming language-specific details, which are not meaningful for algorithm learning. Therefore, this article only provides the implementation of a sum segment tree. If you need other scenarios like finding maximum values, you can modify the aggregation logic in the code or use the AllInOneSegmentTree universal template provided at the end of the article.

3. Segment tree interval updates can be interval assignment (Assign) or interval increment (Increment).

For example, in the array [1, 2, 3, 4, 5], assigning all elements within the index interval [1, 3] to 10 is called interval assignment, resulting in [1, 10, 10, 10, 5]. Increasing all elements within the index interval [1, 3] by 1 is called interval increment, resulting in [1, 3, 4, 5, 5].

These two scenarios are common in algorithm problems, and this article will provide implementations for both.

The main API of the segment tree we implemented previously is as follows:

class SegmentTree {

    // initialize the segment tree
    public SegmentTree(int[] nums, Function<Integer, Integer> merge) {}

    // query the aggregated value of the closed interval [qL, qR], time complexity O(logN)
    public int query(int qL, int qR) {}
    
    // single point update, set nums[i] = val, time complexity O(logN)
    public void update(int i, int val) {}
}

This article will implement the following two types of segment trees:

// interval increment segment tree
class IncrSegmentTree {

    // initialize the dynamic segment tree
    public IncrSegmentTree(int start, int end, int defaultValue) {}

    // increment the closed interval [qL, qR] by
    // delta (can be negative), time complexity
    public void rangeAdd(int qL, int qR, int delta) {}

    // query the sum of the closed interval [qL, qR], time complexity O(logN)
    public int query(int qL, int qR) {}
}

// interval assignment segment tree
class AssignSegmentTree {

    // initialize the dynamic segment tree
    public AssignSegmentTree(int start, int end, int defaultValue) {}

    // assign the closed interval [qL, qR] to val, time complexity O(logN)
    public void rangeUpdate(int qL, int qR, int val) {}

    // query the sum of the closed interval [qL, qR], time complexity O(logN)
    public int query(int qL, int qR) {}
}

The implementation logic of rangeAdd and rangeUpdate is very similar. In theory, they can be implemented in a single class. However, combining the two logics would complicate the code and increase the understanding cost. In actual algorithm problems, usually only one of range addition or range update is used, not both simultaneously. Therefore, this article separates them into two classes for easier understanding of their principles.

At the end of this article, a universal segment tree template AllInOneSegmentTree will be provided. It includes all the aforementioned APIs and all optimizations for segment trees, which can be directly used during coding tests.