18. Segment Tree

Theory

A segment tree is a binary tree where each node stores an aggregate (sum, min, max, gcd, etc.) over a contiguous range of the input array. It supports range queries and point updates in O(log n) time.

See also: Data Structures - Tree for general tree concepts.

When FAANG asks: range sum with point updates (LC 307) or range min/max queries on static arrays — segment tree or Fenwick tree. If the array is static, prefix sum is O(1) per query and simpler. Segment trees also appear in "count of smaller elements to the right" style problems (LC 315).

Lazy propagation extends the segment tree to range updates (add/multiply every element in a range) while keeping queries at O(log n). Each node stores a pending tag that is pushed to children only when needed.

Problems at a glance

LC	Problem
307	Range Sum Query - Mutable	↗
303	Range Sum Query - Immutable	↗
315	Count of Smaller Numbers After Self	↗
729	My Calendar I	↗
850	Rectangle Area II	↗
1622	Fancy Sequence	↗

---

Problems

Problem 1: Range Sum Query - Mutable (Leetcode:307)

Problem Statement

Given an integer array nums, handle multiple queries of the following types:

1. Update the value of an element in nums.
2. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

• NumArray(int[] nums) Initializes the object with the integer array nums.
• void update(int index, int val) Updates the value of nums[index] to be val.
• int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Example 1:

Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]

Explanation
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2); // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8

Constraints:

• 1 <= nums.length <= 3 * 104
• -100 <= nums[i] <= 100
• 0 <= index < nums.length
• -100 <= val <= 100
• 0 <= left <= right < nums.length
• At most 3 * 104 calls will be made to update and sumRange.

Code and Explanation

Approach 1Approach 2

class NumArray:
    def __init__(self, nums: list[int]):
        self.n = len(nums)
        self.nums = nums[:]
        self.tree = [0] * (self.n + 1)

        for i, val in enumerate(nums):
            self._add(i, val)

    def _add(self, i: int, delta: int) -> None:
        i += 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    def _prefix(self, i: int) -> int:
        i += 1
        total = 0
        while i:
            total += self.tree[i]
            i -= i & -i
        return total

    def update(self, index: int, val: int) -> None:
        self._add(index, val - self.nums[index])
        self.nums[index] = val

    def sumRange(self, left: int, right: int) -> int:
        return self._prefix(right) - (self._prefix(left - 1) if left else 0)

Explanation:

1. A Fenwick tree (Binary Indexed Tree) stores prefix sums in a compact array using the i & -i trick to jump between responsible ranges.
2. update applies a delta at one index; each affected tree cell is updated in O(log n).
3. sumRange(left, right) returns prefix(right) - prefix(left - 1), giving the inclusive range sum in O(log n).
4. Fenwick trees are the preferred choice for range sum + point update because they use less memory and simpler code than a segment tree.

Time: build O(n log n), update/query O(log n)  |  Space: O(n)

class NumArray:
    def __init__(self, nums: list[int]):
        self.n = len(nums)
        self.size = 1
        while self.size < self.n:
            self.size *= 2
        self.tree = [0] * (2 * self.size)

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

    def update(self, index: int, val: int) -> None:
        pos = self.size + index
        self.tree[pos] = val
        pos //= 2
        while pos:
            self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]
            pos //= 2

    def sumRange(self, left: int, right: int) -> int:
        left += self.size
        right += self.size
        total = 0
        while left <= right:
            if left % 2 == 1:
                total += self.tree[left]
                left += 1
            if right % 2 == 0:
                total += self.tree[right]
                right -= 1
            left //= 2
            right //= 2
        return total

Explanation:

1. Build an iterative segment tree where leaf nodes hold array values and each parent stores the sum of its two children.
2. Point update: walk from the updated leaf to the root, recomputing sums at every ancestor — O(log n).
3. Range sum query: decompose [left, right] into O(log n) fully covered node ranges and add their stored sums.
4. This is the canonical segment tree template for range sum query with point updates.

Time: build O(n), update/query O(log n)  |  Space: O(n)

Problem 2: Range Sum Query - Immutable (Leetcode:303)

Problem Statement

Given an integer array nums, handle multiple queries of the following type:

1. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

• NumArray(int[] nums) Initializes the object with the integer array nums.
• int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Example 1:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

Constraints:

• 1 <= nums.length <= 104
• -105 <= nums[i] <= 105
• 0 <= left <= right < nums.length
• At most 104 calls will be made to sumRange.

Code and Explanation

Approach 1Approach 2

class NumArray:
    def __init__(self, nums: list[int]):
        self.prefix = [0]
        for val in nums:
            self.prefix.append(self.prefix[-1] + val)

    def sumRange(self, left: int, right: int) -> int:
        return self.prefix[right + 1] - self.prefix[left]

Explanation:

1. Precompute a prefix sum array where prefix[i] is the sum of nums[0..i-1].
2. The sum of nums[left..right] equals prefix[right + 1] - prefix[left] — a single subtraction.
3. Because the array never changes, there is no need for a dynamic structure.
4. This is the optimal solution: O(1) per query after O(n) preprocessing.

Time: build O(n), query O(1)  |  Space: O(n)

class NumArray:
    def __init__(self, nums: list[int]):
        self.n = len(nums)
        self.size = 1
        while self.size < self.n:
            self.size *= 2
        self.tree = [0] * (2 * self.size)

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

    def sumRange(self, left: int, right: int) -> int:
        left += self.size
        right += self.size
        total = 0
        while left <= right:
            if left % 2 == 1:
                total += self.tree[left]
                left += 1
            if right % 2 == 0:
                total += self.tree[right]
                right -= 1
            left //= 2
            right //= 2
        return total

Explanation:

1. Build a segment tree once at construction time — no updates are needed since the array is immutable.
2. Each internal node stores the sum of its range; leaves hold individual elements.
3. sumRange walks the tree in O(log n), merging fully covered child ranges.
4. Overkill for this problem, but demonstrates the static range sum query segment tree pattern used when updates will be added later (LC 307).

Time: build O(n), query O(log n)  |  Space: O(n)

Problem 3: Count of Smaller Numbers After Self (Leetcode:315)

Problem Statement

Given an integer array nums, return an integer array counts where counts[i] is the number of smaller elements to the right of nums[i].

Example 1:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Example 2:

Input: nums = [-1]
Output: [0]

Example 3:

Input: nums = [-1,-1]
Output: [0,0]

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

Code and Explanation

Approach 1Approach 2

class Solution:
    def countSmaller(self, nums: list[int]) -> list[int]:
        n = len(nums)
        counts = [0] * n
        for i in range(n):
            for j in range(i + 1, n):
                if nums[j] < nums[i]:
                    counts[i] += 1
        return counts

Explanation:

1. For each index i, scan every element to its right and count how many are strictly smaller.
2. Direct translation of the problem statement — no extra data structures.
3. Works correctly for all inputs but does not scale to n = 10⁵.

Time: O(n²)  |  Space: O(1) extra

class Solution:
    def countSmaller(self, nums: list[int]) -> list[int]:
        if not nums:
            return []

        coords = sorted(set(nums))
        rank = {v: i + 1 for i, v in enumerate(coords)}
        m = len(coords)
        tree = [0] * (m + 1)

        def add(i: int) -> None:
            while i <= m:
                tree[i] += 1
                i += i & -i

        def query(i: int) -> int:
            total = 0
            while i:
                total += tree[i]
                i -= i & -i
            return total

        counts = [0] * len(nums)
        for i in range(len(nums) - 1, -1, -1):
            r = rank[nums[i]]
            counts[i] = query(r - 1)
            add(r)
        return counts

Explanation:

1. Coordinate-compress values to ranks 1..m so the Fenwick tree indexes fit in O(n) space.
2. Process elements right to left: before inserting nums[i], query how many ranks < rank(nums[i]) are already in the tree — that is the answer for index i.
3. Then add(rank(nums[i])) to record this value for future leftward indices.
4. Each query and update is O(log n), giving O(n log n) total — the standard Fenwick tree inversion-count pattern.

Time: O(n log n)  |  Space: O(n)

Problem 4: Range Minimum Query - Mutable

Problem Statement

Given an integer array nums, support two operations:

1. Update the value at a single index.
2. Query the minimum value in a range [left, right] inclusive.

Implement:

• RMQ(nums) — initialize with the array.
• update(index, val) — set nums[index] = val.
• queryMin(left, right) — return min(nums[left..right]).

Example:

Input: nums = [2, 5, 1, 9, 3]
queryMin(0, 4) → 1
update(2, 7) // nums = [2, 5, 7, 9, 3]
queryMin(0, 4) → 2

Constraints:

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• At most 105 update and query calls.

Code and Explanation

Approach 1Approach 2

class RMQ:
    def __init__(self, nums: list[int]):
        self.nums = nums[:]

    def update(self, index: int, val: int) -> None:
        self.nums[index] = val

    def queryMin(self, left: int, right: int) -> int:
        return min(self.nums[left:right + 1])

Explanation:

1. Store the array and scan the requested range linearly on each query.
2. update is O(1); queryMin is O(n) in the worst case.
3. Acceptable only for small arrays or very few queries — illustrates why a tree structure is needed.

Time: update O(1), query O(n)  |  Space: O(n)

class RMQ:
    def __init__(self, nums: list[int]):
        self.n = len(nums)
        self.size = 1
        while self.size < self.n:
            self.size *= 2
        self.tree = [float("inf")] * (2 * self.size)

        for i, val in enumerate(nums):
            self.tree[self.size + i] = val
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = min(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, index: int, val: int) -> None:
        pos = self.size + index
        self.tree[pos] = val
        pos //= 2
        while pos:
            self.tree[pos] = min(self.tree[2 * pos], self.tree[2 * pos + 1])
            pos //= 2

    def queryMin(self, left: int, right: int) -> int:
        left += self.size
        right += self.size
        result = float("inf")
        while left <= right:
            if left % 2 == 1:
                result = min(result, self.tree[left])
                left += 1
            if right % 2 == 0:
                result = min(result, self.tree[right])
                right -= 1
            left //= 2
            right //= 2
        return result

Explanation:

1. Build a segment tree where each node stores the minimum of its range instead of the sum.
2. Point update: set the leaf and propagate min(left, right) upward — O(log n).
3. Range min query: decompose [left, right] into O(log n) fully covered nodes and take the minimum of their values.
4. This is the min analogue of LC 307 — same tree shape, different merge function (min vs +).

Time: build O(n), update/query O(log n)  |  Space: O(n)

Problem 5: My Calendar I (Leetcode:729)

Problem Statement

Implement the MyCalendar class to store your bookings. A booking can only be added if the requested time slot is not already booked.

• MyCalendar() Initializes the calendar object.
• boolean book(int start, int end) Returns true if the event can be added to the calendar and does so. Otherwise, return false and do not add the event. The half-open interval [start, end) is used.

Example 1:

Input: ["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output: [null, true, false, true]
Explanation:
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, time slot [15, 20) is already booked.
myCalendar.book(20, 30); // return True, time slot [20, 30) is available.

Constraints:

• 0 <= start < end <= 109
• At most 1000 calls will be made to book.

Code and Explanation

Approach 1Approach 2

class MyCalendar:
    def __init__(self):
        self.bookings: list[tuple[int, int]] = []

    def book(self, start: int, end: int) -> bool:
        for s, e in self.bookings:
            if start < e and s < end:
                return False
        self.bookings.append((start, end))
        return True

Explanation:

1. Store every confirmed booking as a (start, end) pair.
2. Two intervals [start, end) and [s, e) overlap iff start < e and s < end.
3. Check all existing bookings before accepting a new one.
4. Simple and correct for the constraint of 1000 calls, but O(n) per booking.

Time: O(n) per book  |  Space: O(n)

class MyCalendar:
    def __init__(self):
        self.tree: dict[int, int] = {}

    def _query(self, node: int, l: int, r: int, ql: int, qr: int) -> int:
        if qr <= l or r <= ql:
            return 0
        if ql <= l and r <= qr:
            return self.tree.get(node, 0)
        mid = (l + r) // 2
        return max(
            self._query(node * 2, l, mid, ql, qr),
            self._query(node * 2 + 1, mid, r, ql, qr),
        )

    def _update(self, node: int, l: int, r: int, ql: int, qr: int, val: int) -> None:
        if qr <= l or r <= ql:
            return
        if ql <= l and r <= qr:
            self.tree[node] = max(self.tree.get(node, 0), val)
            return
        mid = (l + r) // 2
        self._update(node * 2, l, mid, ql, qr, val)
        self._update(node * 2 + 1, mid, r, ql, qr, val)
        self.tree[node] = max(
            self.tree.get(node * 2, 0),
            self.tree.get(node * 2 + 1, 0),
        )

    def book(self, start: int, end: int) -> bool:
        if self._query(1, 0, 10**9, start, end - 1) > 0:
            return False
        self._update(1, 0, 10**9, start, end - 1, 1)
        return True

Explanation:

1. Use a segment tree over the timeline [0, 10⁹] where each node stores whether its range is booked (max = 1) or free (max = 0).
2. Before booking [start, end), query whether any part of that range is already occupied.
3. If free, update the range to mark it booked by setting values to 1.
4. The tree is stored in a hash map (dynamic node allocation) since the domain is large but only O(k log W) nodes are ever created for k bookings.

Time: O(log W) per book, W = 10⁹  |  Space: O(k log W)

Problem 6: Rectangle Area II (Leetcode:850)

Problem Statement

You are given a 2D array of axis-aligned rectangles. Each rectangle[i] = [xi1, yi1, xi2, yi2] denotes the ith rectangle where (xi1, yi1) are the coordinates of the bottom-left corner, and (xi2, yi2) are the coordinates of the top-right corner.

Calculate the total area covered by all rectangles in the plane. Any area covered by two or more rectangles should only be counted once.

Return the total area. Since the answer may be too large, return it modulo** 109 + 7.

Example 1:

Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.

Example 2:

Input: rectangles = [[0,0,1000000000,1000000000]]
Output: 49
Explanation: The answer is 1018 modulo (109 + 7), which is 49.

Constraints:

• 1 <= rectangles.length <= 200
• rectanges[i].length == 4
• 0 <= xi1, yi1, xi2, yi2 <= 109
• xi1 <= xi2
• yi1 <= yi2
• All rectangles have non zero area.

Code and Explanation

Approach 1Approach 2

class Solution:
    def rectangleArea(self, rectangles: list[list[int]]) -> int:
        MOD = 10**9 + 7
        xs = sorted(set(x for r in rectangles for x in (r[0], r[2])))
        ys = sorted(set(y for r in rectangles for y in (r[1], r[3])))

        covered = set()
        for x1, y1, x2, y2 in rectangles:
            for i in range(len(xs) - 1):
                if xs[i] >= x1 and xs[i + 1] <= x2:
                    for j in range(len(ys) - 1):
                        if ys[j] >= y1 and ys[j + 1] <= y2:
                            covered.add((xs[i], ys[j], xs[i + 1], ys[j + 1]))

        area = 0
        for x1, y1, x2, y2 in covered:
            area = (area + (x2 - x1) * (y2 - y1)) % MOD
        return area

Explanation:

1. Coordinate-compress all unique x and y coordinates to form a grid of atomic cells.
2. For each rectangle, mark every grid cell it fully covers in a set (deduplication handles overlaps).
3. Sum the area of all covered cells.
4. Correct but slow — O(R · X · Y) where R = number of rectangles and X, Y = compressed grid sizes. Works for small inputs only.

Time: O(R · X · Y)  |  Space: O(X · Y)

class Solution:
    def rectangleArea(self, rectangles: list[list[int]]) -> int:
        MOD = 10**9 + 7
        xs = sorted(set(x for r in rectangles for x in (r[0], r[2])))
        x_id = {x: i for i, x in enumerate(xs)}
        n = len(xs) - 1
        if n <= 0:
            return 0

        events = []
        for x1, y1, x2, y2 in rectangles:
            events.append((y1, 1, x_id[x1], x_id[x2] - 1))
            events.append((y2, -1, x_id[x1], x_id[x2] - 1))
        events.sort()

        size = 1
        while size < n:
            size *= 2
        cover = [0] * (2 * size)
        length = [0] * (2 * size)

        def push_up(node: int, l: int, r: int) -> None:
            if cover[node] > 0:
                length[node] = xs[r + 1] - xs[l]
            elif l == r:
                length[node] = 0
            else:
                length[node] = length[2 * node] + length[2 * node + 1]

        def update(node: int, l: int, r: int, ql: int, qr: int, delta: int) -> None:
            if qr < l or r < ql:
                return
            if ql <= l and r <= qr:
                cover[node] += delta
            else:
                mid = (l + r) // 2
                update(2 * node, l, mid, ql, qr, delta)
                update(2 * node + 1, mid + 1, r, ql, qr, delta)
            push_up(node, l, r)

        total = 0
        prev_y = events[0][0]
        for y, typ, left, right in events:
            total = (total + length[1] * (y - prev_y)) % MOD
            update(1, 0, n - 1, left, right, typ)
            prev_y = y
        return total

Explanation:

1. Sweep line on y: each rectangle adds a +1 event at its bottom edge and a −1 event at its top edge.
2. Maintain a segment tree with lazy propagation over compressed x-coordinates. Each node tracks a cover count (how many active rectangles span it) and the length of x-interval currently covered.
3. Between consecutive y-events, the total covered x-length (length[1]) is constant; multiply by the y-strip height and accumulate area.
4. cover > 0 means the entire node range is covered; otherwise combine children. This is the classic lazy segment tree sweep-line template.

Time: O(n² log n) for n rectangles  |  Space: O(n)

Problem 7: Fancy Sequence (Leetcode:1622)

Problem Statement

Write an API that generates fancy sequences using the append, addAll, and multAll operations.

Implement the Fancy class:

• Fancy() Initializes the object with an empty sequence.
• void append(val) Appends an integer val to the end of the sequence.
• void addAll(inc) Increments all existing values in the sequence by an integer inc.
• void multAll(m) Multiplies all existing values in the sequence by an integer m.
• int getIndex(idx) Gets the current value at index idx (0-indexed) of the sequence modulo 109 + 7. If the index is greater or equal than the length of the sequence, return -1.

Example 1:

Input
["Fancy", "append", "addAll", "append", "multAll", "getIndex", "addAll", "append", "multAll", "getIndex", "getIndex", "getIndex"]
[[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]]
Output
[null, null, null, null, null, 10, null, null, null, 26, 34, 20]

Explanation
Fancy fancy = new Fancy();
fancy.append(2); // fancy sequence: [2]
fancy.addAll(3); // fancy sequence: [2+3] -> [5]
fancy.append(7); // fancy sequence: [5, 7]
fancy.multAll(2); // fancy sequence: [52, 72] -> [10, 14]
fancy.getIndex(0); // return 10
fancy.addAll(3); // fancy sequence: [10+3, 14+3] -> [13, 17]
fancy.append(10); // fancy sequence: [13, 17, 10]
fancy.multAll(2); // fancy sequence: [132, 172, 10*2] -> [26, 34, 20]
fancy.getIndex(0); // return 26
fancy.getIndex(1); // return 34
fancy.getIndex(2); // return 20

Constraints:

• 1 <= val, inc, m <= 100
• 0 <= idx <= 105
• At most 105 calls total will be made to append, addAll, multAll, and getIndex.

Code and Explanation

Approach 1Approach 2

class Fancy:
    def __init__(self):
        self.arr: list[int] = []
        self.mod = 10**9 + 7

    def append(self, val: int) -> None:
        self.arr.append(val)

    def addAll(self, inc: int) -> None:
        self.arr = [(x + inc) % self.mod for x in self.arr]

    def multAll(self, m: int) -> None:
        self.arr = [(x * m) % self.mod for x in self.arr]

    def getIndex(self, idx: int) -> int:
        return self.arr[idx] if idx < len(self.arr) else -1

Explanation:

1. Store the sequence literally and apply addAll / multAll to every element immediately.
2. append and getIndex are O(1); each bulk operation costs O(n) where n is the current sequence length.
3. With up to 10⁵ total calls this can degrade to O(n²) overall — correct but too slow at scale.

Time: append/getIndex O(1), addAll/multAll O(n)  |  Space: O(n)

class Fancy:
    def __init__(self):
        self.arr: list[int] = []
        self.lazy_add = 0
        self.lazy_mult = 1
        self.mod = 10**9 + 7

    def append(self, val: int) -> None:
        inv = pow(self.lazy_mult, self.mod - 2, self.mod)
        self.arr.append((val - self.lazy_add) * inv % self.mod)

    def addAll(self, inc: int) -> None:
        self.lazy_add = (self.lazy_add + inc) % self.mod

    def multAll(self, m: int) -> None:
        self.lazy_add = (self.lazy_add * m) % self.mod
        self.lazy_mult = (self.lazy_mult * m) % self.mod

    def getIndex(self, idx: int) -> int:
        if idx >= len(self.arr):
            return -1
        return (self.arr[idx] * self.lazy_mult + self.lazy_add) % self.mod

Explanation:

1. Defer bulk operations using lazy propagation tags: a global multiplier lazy_mult and offset lazy_add applied to all existing elements.
2. Each stored value is normalized at append time so that stored[i] * lazy_mult + lazy_add gives the true current value.
3. addAll bumps the lazy offset; multAll scales both the offset and multiplier — O(1) each, no array scan.
4. getIndex applies the pending affine transform to one element — the same lazy-tag idea used in segment trees for range add/multiply updates.

Time: all operations O(1)  |  Space: O(n)