Segment Tree & Fenwick Tree

Problem: Support update(index, val) and sumRange(left, right) on an array, both fast.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 3 * 10⁴ · -100 ≤ nums[i] ≤ 100 · 0 ≤ index < nums.length · -100 ≤ val ≤ 100 · 0 ≤ left ≤ right < nums.length · At most 3 * 10⁴ calls will be made to update and sumRange.

From brute force to the pattern: Recomputing sums per query is O(n); the Fenwick tree makes both operations O(log n).

Spot it: Prefix sums make queries O(1) but updates O(n). A Fenwick (binary indexed) tree stores partial sums over blocks sized by the lowest set bit, so both operations take O(log n).

Why not another pattern? A plain prefix-sum array needs an O(n) rebuild per update; recomputing sums per query is O(n).

Approach:

1. tree is 1-indexed; add(i, delta): while i ≤ n: tree[i] += delta, i += i & −i.
2. prefix(i): while i > 0: sum tree[i], i −= i & −i.
3. update: add the difference; sumRange(l, r) = prefix(r + 1) − prefix(l).

class NumArray:
    def __init__(self, nums: List[int]):
        self.n = len(nums)
        self.nums = nums[:]
        self.tree = [0] * (self.n + 1)  # 1-indexed Fenwick tree
        for i, x in enumerate(nums):
            self._add(i + 1, x)

    def _add(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i  # next block that covers position i

    def _prefix(self, i):  # sum of the first i elements
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i  # drop the lowest set bit
        return total

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

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

What the code is doing, line by line:

1. tree[i] holds the sum of the i & −i elements ending at position i.
2. Updating walks up through every block containing the position; prefix queries walk down through disjoint blocks.
3. Both walks visit at most log n nodes.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Single element.
• Updating to the same value.
• Range of the whole array.

Complexity: O(log n) per update and query, O(n log n) to build (or O(n) with a smarter build), O(n) space.

Problem: For each element, count how many elements to its right are smaller.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · -10⁴ ≤ nums[i] ≤ 10⁴

From brute force to the pattern: All pairs: O(n²). Fenwick tree (or merge sort counting): O(n log n).

Spot it: Walk from the right, inserting values into a Fenwick tree indexed by rank (coordinate compression). Before inserting x, the prefix sum up to rank(x) − 1 is the number of smaller values already seen, i.e. to its right.

Why not another pattern? Checking all pairs is O(n²).

Approach:

1. Rank values: rank = {v: i + 1} over sorted distinct values.
2. From right to left: counts[i] = prefix(rank[x] − 1); then add(rank[x], 1).

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        rank = {v: i + 1 for i, v in enumerate(sorted(set(nums)))}  # compress values to 1..m
        m = len(rank)
        tree = [0] * (m + 1)
        counts = [0] * len(nums)
        for i in range(len(nums) - 1, -1, -1):  # right to left
            r = rank[nums[i]] - 1
            seen_smaller = 0
            while r > 0:
                seen_smaller += tree[r]  # how many smaller values are to the right
                r -= r & -r
            counts[i] = seen_smaller
            r = rank[nums[i]]
            while r <= m:
                tree[r] += 1  # record nums[i]
                r += r & -r
        return counts

What the code is doing, line by line:

1. Ranks keep the tree size at the number of distinct values (values can be negative).
2. Strictly smaller means querying up to rank − 1.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Duplicates (not counted as smaller).
• Negative values.
• Sorted ascending → all zeros.

Complexity: O(n log n) time, O(n) space.

Problem: Find the longest strictly increasing subsequence where adjacent elements differ by at most k.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i], k ≤ 10⁵

From brute force to the pattern: The pairwise DP is O(n²); a value-indexed segment tree is O(n log V).

Spot it: LIS ending at value v extends any subsequence ending at a value in [v − k, v − 1]. That's a range-max query plus a point update over values → a segment tree indexed by value.

Why not another pattern? The O(n²) LIS DP is too slow for n = 10⁵; patience sorting can't express the ≤ k gap rule.

Approach:

1. Segment tree over values 1..max.
2. For each x: cur = 1 + max(query(x − k, x − 1)); update(x, cur).
3. Answer: the maximum cur.

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        size = 1
        while size <= max(nums):
            size *= 2
        tree = [0] * (2 * size)  # iterative max segment tree over values 0..size-1

        def query(lo, hi):  # max of best[lo..hi]
            res = 0
            lo += size
            hi += size + 1
            while lo < hi:
                if lo & 1:
                    res = max(res, tree[lo])
                    lo += 1
                if hi & 1:
                    hi -= 1
                    res = max(res, tree[hi])
                lo //= 2
                hi //= 2
            return res

        def update(i, val):
            i += size
            tree[i] = max(tree[i], val)
            i //= 2
            while i:
                tree[i] = max(tree[2 * i], tree[2 * i + 1])
                i //= 2

        best = 0
        for x in nums:
            cur = 1 + query(max(0, x - k), x - 1)  # extend the best chain ending k or less below x
            update(x, cur)
            best = max(best, cur)
        return best

What the code is doing, line by line:

1. tree leaves hold the best LIS length ending at each value; internal nodes hold maxima of their ranges.
2. The query covers exactly the values that may come right before x (strictly smaller, gap ≤ k).
3. Processing in array order keeps the subsequence order correct.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Equal values (strictly increasing: no chain).
• k = 1 (consecutive values only).
• Single element.

Complexity: O(n log V) time, O(V) space (V = max(nums)).

Problem: Count subarrays whose sum lies in [lower, upper].

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · -2³¹ ≤ nums[i] ≤ 2³¹ - 1 · -10⁵ ≤ lower ≤ upper ≤ 10⁵ · The answer is guaranteed to fit in a 32-bit integer.

From brute force to the pattern: Every subarray: O(n²). Fenwick tree or merge sort: O(n log n).

Spot it: A subarray sum is P[j] − P[i] for prefix sums. For each j, count earlier prefixes in [P[j] − upper, P[j] − lower]: a range count over values seen so far → Fenwick tree with coordinate compression.

Why not another pattern? All subarrays: O(n²).

Approach:

1. Prefix sums P[0..n]; compress all P values.
2. For each P[j] in order: count compressed prefixes with value in the window (two bisects on the sorted values, two prefix queries); then insert P[j].

from bisect import bisect_left, bisect_right
from itertools import accumulate

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        prefix = [0] + list(accumulate(nums))
        values = sorted(set(prefix))
        m = len(values)
        tree = [0] * (m + 1)

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

        def count(i):  # prefixes stored among the first i sorted values
            total = 0
            while i > 0:
                total += tree[i]
                i -= i & -i
            return total

        result = 0
        for p in prefix:
            lo = bisect_left(values, p - upper)  # first value >= p - upper
            hi = bisect_right(values, p - lower)  # past the last value <= p - lower
            result += count(hi) - count(lo)  # earlier prefixes making a sum in range
            add(bisect_left(values, p) + 1)
        return result

What the code is doing, line by line:

1. lower ≤ P[j] − P[i] ≤ upper ⇔ P[j] − upper ≤ P[i] ≤ P[j] − lower.
2. Binary search maps the value window to a rank window; the Fenwick tree counts inserted prefixes in it.
3. Inserting after counting ensures only i < j are counted.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Negative numbers.
• lower == upper.
• Single element.

Complexity: O(n log n) time, O(n) space.

Problem: Count pairs i < j with nums[i] > 2 · nums[j].

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 5 * 10⁴ · -2³¹ ≤ nums[i] ≤ 2³¹ - 1

From brute force to the pattern: All pairs: O(n²). Fenwick: O(n log n).

Spot it: Scan left to right; for each j ask "how many earlier values exceed 2 · nums[j]?" → Fenwick tree over ranks of all values.

Why not another pattern? All pairs: O(n²).

Approach:

1. Sort distinct values.
2. For each x: count inserted values > 2x = inserted − (inserted values ≤ 2x).
3. Insert x.

from bisect import bisect_left, bisect_right

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        values = sorted(set(nums))
        m = len(values)
        tree = [0] * (m + 1)
        result = 0
        for seen, x in enumerate(nums):
            i = bisect_right(values, 2 * x)  # values <= 2x occupy ranks 1..i
            small = 0
            while i > 0:
                small += tree[i]
                i -= i & -i
            result += seen - small  # earlier values greater than 2x
            i = bisect_left(values, x) + 1
            while i <= m:
                tree[i] += 1
                i += i & -i
        return result

What the code is doing, line by line:

1. seen is the number of earlier elements; subtracting those ≤ 2x leaves those > 2x.
2. Ranks come from the array's own values; bisect_right finds how many are ≤ 2x even though 2x itself may not be a value.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Negative numbers (2x can be smaller than x).
• Large values (no overflow in Python).
• Duplicates.

Complexity: O(n log n) time, O(n) space.

Problem: After each single-character update, return the length of the longest run of one repeated character.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 10⁵ · s consists of lowercase English letters. · k == queryCharacters.length == queryIndices.length · 1 ≤ k ≤ 10⁵ · queryCharacters consists of lowercase English letters. · 0 ≤ queryIndices[i] < s.length

From brute force to the pattern: Rescanning after every query is O(nk); the segment tree is O(k log n).

Spot it: Each update changes one position; the answer is a global property. A segment tree where each node knows its best run, its run from the left edge and its run to the right edge can be merged in O(1), so each update costs O(log n).

Why not another pattern? Rescanning the string after each update is O(n · k).

Approach:

1. Node for [lo, hi]: pre, suf, best.
2. Merge L = [lo, mid], R = [mid+1, hi]: join = s[mid] == s[mid+1]; best = max(L.best, R.best, L.suf + R.pref if join).
3. pre = L.pre + R.pre if L.pre covers all of L and join, else L.pre; symmetric for suf.
4. Update a leaf and re-merge up to the root; report best[root].

class Solution:
    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:
        n = len(s)
        chars = list(s)
        pre = [0] * (4 * n)
        suf = [0] * (4 * n)
        best = [0] * (4 * n)

        def pull(node, lo, hi):
            mid = (lo + hi) // 2
            L, R = 2 * node, 2 * node + 1
            join = chars[mid] == chars[mid + 1]  # can runs continue across the middle?
            best[node] = max(best[L], best[R], suf[L] + pre[R] if join else 0)
            pre[node] = pre[L] + pre[R] if join and pre[L] == mid - lo + 1 else pre[L]
            suf[node] = suf[R] + suf[L] if join and suf[R] == hi - mid else suf[R]

        def build(node, lo, hi):
            if lo == hi:
                pre[node] = suf[node] = best[node] = 1
                return
            mid = (lo + hi) // 2
            build(2 * node, lo, mid)
            build(2 * node + 1, mid + 1, hi)
            pull(node, lo, hi)

        def update(node, lo, hi, i):
            if lo == hi:
                return  # a single character is always a run of 1
            mid = (lo + hi) // 2
            if i <= mid:
                update(2 * node, lo, mid, i)
            else:
                update(2 * node + 1, mid + 1, hi, i)
            pull(node, lo, hi)  # recombine on the way up

        build(1, 0, n - 1)
        result = []
        for ch, i in zip(queryCharacters, queryIndices):
            chars[i] = ch
            update(1, 0, n - 1, i)
            result.append(best[1])
        return result

What the code is doing, line by line:

1. A run either lies inside one half or crosses the middle; crossing runs are L.suf + R.pref.
2. A node's prefix run extends into the right half only if the whole left half is one run and the middle characters match.
3. Only the O(log n) nodes on the path from the updated leaf change.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Updating to the same character.
• Length-1 string.
• Runs joining across the middle.

Complexity: O(n + k log n) time, O(n) space.

Problem: Insert obstacles on a line; for each query, can a block of size sz fit inside [0, x] without crossing an obstacle?

Solve it on LeetCode ↗

Constraints: 1 ≤ queries.length ≤ 15 * 10⁴ · 2 ≤ queries[i].length ≤ 3 · 1 ≤ queries[i][0] ≤ 2 · 1 ≤ x, sz ≤ min(5 * 10⁴, 3 * queries.length) · The input is generated such that for queries of type 1, no obstacle exists at distance x when the query is asked. · The input is generated such that there is at least one query of type 2.

From brute force to the pattern: Scanning obstacles per query is O(q²); a max segment tree over gaps makes queries O(log X).

Spot it: The answer is whether the largest free gap inside [0, x] is ≥ sz. Keep the obstacles sorted (with 0 as a virtual obstacle); store each obstacle's gap to its predecessor at its position in a max segment tree. A query is the max over obstacles ≤ x, plus the tail gap x − last.

Why not another pattern? Scanning the obstacles per query is O(n) each.

Approach:

1. obstacles = [0] (sorted); segment tree over positions 0..max x.
2. Insert x between p and q: gap[x] = x − p, gap[q] = q − x (if q exists).
3. Query (x, sz): p = last obstacle ≤ x; fits iff max(tree max over [0, p], x − p) ≥ sz.

from bisect import bisect_right, insort

class Solution:
    def getResults(self, queries: List[List[int]]) -> List[bool]:
        top = max(q[1] for q in queries) + 1
        size = 1
        while size < top:
            size *= 2
        tree = [0] * (2 * size)  # tree over positions: gap ending at an obstacle

        def set_gap(i, val):
            i += size
            tree[i] = val
            i //= 2
            while i:
                tree[i] = max(tree[2 * i], tree[2 * i + 1])
                i //= 2

        def max_upto(hi):  # max gap stored at positions 0..hi
            res = 0
            lo, hi = size, hi + size + 1
            while lo < hi:
                if lo & 1:
                    res = max(res, tree[lo])
                    lo += 1
                if hi & 1:
                    hi -= 1
                    res = max(res, tree[hi])
                lo //= 2
                hi //= 2
            return res

        obstacles = [0]  # the origin acts as an obstacle
        result = []
        for q in queries:
            x = q[1]
            k = bisect_right(obstacles, x)
            prev = obstacles[k - 1]
            if q[0] == 1:
                set_gap(x, x - prev)  # new gap ending at x
                if k < len(obstacles):
                    nxt = obstacles[k]
                    set_gap(nxt, nxt - x)  # the next obstacle's gap shrinks
                insort(obstacles, x)
            else:
                biggest = max(max_upto(prev), x - prev)  # gaps fully inside [0, x], plus the tail
                result.append(biggest >= q[2])
        return result

What the code is doing, line by line:

1. Every gap between consecutive obstacles is stored at its right end, so "gaps inside [0, x]" are those stored at positions ≤ the last obstacle before x.
2. The tail from the last obstacle to x is not stored and is added separately.
3. Blocks may touch obstacles, so a gap of exactly sz fits.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No obstacles yet (the whole [0, x] is free).
• A block exactly equal to a gap.
• Obstacles inserted out of order.

Complexity: O(q log X) for the tree, plus O(q) per sorted-list insert (O(log) with a balanced tree).

Problem: Each fruit (in order) goes to the leftmost unused basket with capacity ≥ its quantity. Count fruits left unplaced.

Solve it on LeetCode ↗

Constraints: n == fruits.length == baskets.length · 1 ≤ n ≤ 10⁵ · 1 ≤ fruits[i], baskets[i] ≤ 10⁹

From brute force to the pattern: Linear scans per fruit: O(n²); tree descent: O(log n) per fruit.

Spot it: "Leftmost index with value ≥ x" with removals → a max segment tree: from the root, go left if the left child's max is enough, else right. Using a basket sets its leaf to 0.

Why not another pattern? Scanning baskets for each fruit is O(n²) with n = 10⁵.

Approach:

1. Build a max tree over capacities (padded to a power of two).
2. For each fruit: if the root max < fruit, unplaced. Otherwise descend to the leftmost fitting leaf and set it to 0.

class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        size = 1
        while size < len(baskets):
            size *= 2
        tree = [0] * (2 * size)
        tree[size:size + len(baskets)] = baskets  # leaves
        for i in range(size - 1, 0, -1):
            tree[i] = max(tree[2 * i], tree[2 * i + 1])
        unplaced = 0
        for f in fruits:
            if tree[1] < f:
                unplaced += 1  # no basket is big enough
                continue
            i = 1
            while i < size:
                i = 2 * i if tree[2 * i] >= f else 2 * i + 1  # prefer the left half
            tree[i] = 0  # this basket is used
            i //= 2
            while i:
                tree[i] = max(tree[2 * i], tree[2 * i + 1])
                i //= 2
        return unplaced

What the code is doing, line by line:

1. Each node holds the largest free capacity in its range.
2. Going left whenever possible finds the leftmost fitting basket.
3. Setting a used basket to 0 removes it from future searches.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All fruits fit.
• A big fruit early blocks the only big basket.
• Equal capacities.

Complexity: O(n log n) time, O(n) space.

Problem: Same trade as Range I, but each query applies it to a substring s[l..r] (padded with 1s). Return the total 1s after the best trade.

Solve it on LeetCode ↗

Constraints: 1 ≤ n == s.length ≤ 10⁵ · 1 ≤ queries.length ≤ 10⁵ · s[i] is either '0' or '1'. · queries[i] = [li, ri] · 0 ≤ li ≤ ri < n

From brute force to the pattern: Recomputing blocks per query is O(nq); a sparse table makes each query O(log n) (for the binary searches).

Spot it: As in Range I, the best gain is the largest sum of two adjacent 0-blocks, now restricted to [l, r]. Inner pairs are fixed, so precompute pair[i] = len[i] + len[i+1] and answer range maxima with a sparse table. Only the first and last blocks can be clipped by the query, so pairs touching them are computed directly.

Why not another pattern? Recomputing blocks per query is O(n) each.

Approach:

1. List 0-blocks (start, end) with lengths; pair[i] and a sparse table for range max.
2. Query: blocks a..b overlapping [l, r] (binary search). If fewer than two, gain 0.
3. Clip len_a, len_b to the query. Candidates: pairs (a, a+1) and (b−1, b) with clipped lengths, and max(pair[a+1..b−2]) from the table.
4. Answer: total 1s in s + best gain.

from bisect import bisect_left, bisect_right

class Solution:
    def maxActiveSectionsAfterTrade(self, s: str, queries: List[List[int]]) -> List[int]:
        ones = s.count("1")
        starts, ends = [], []  # zero blocks
        i = 0
        while i < len(s):
            if s[i] == "0":
                j = i
                while j + 1 < len(s) and s[j + 1] == "0":
                    j += 1
                starts.append(i)
                ends.append(j)
                i = j + 1
            else:
                i += 1
        length = [e - st + 1 for st, e in zip(starts, ends)]
        pair = [length[t] + length[t + 1] for t in range(len(length) - 1)]  # two neighbouring blocks
        table = [pair]  # sparse table: table[j][t] = max of pair[t .. t + 2^j - 1]
        while len(table[-1]) > 1 and (1 << len(table)) <= len(pair):
            prev, half = table[-1], 1 << (len(table) - 1)
            table.append([max(prev[t], prev[t + half]) for t in range(len(prev) - half)])

        def range_max(lo, hi):  # max of pair[lo..hi], 0 if empty
            if lo > hi:
                return 0
            j = (hi - lo + 1).bit_length() - 1
            return max(table[j][lo], table[j][hi - (1 << j) + 1])

        answer = []
        for l, r in queries:
            a = bisect_left(ends, l)  # first block ending at or after l
            b = bisect_right(starts, r) - 1  # last block starting at or before r
            if b - a < 1:
                answer.append(ones)  # fewer than two zero blocks: no useful trade
                continue
            len_a = ends[a] - max(starts[a], l) + 1  # clipped by the query
            len_b = min(ends[b], r) - starts[b] + 1
            if b == a + 1:
                gain = len_a + len_b
            else:
                gain = max(len_a + length[a + 1], length[b - 1] + len_b, range_max(a + 1, b - 2))
            answer.append(ones + gain)
        return answer

What the code is doing, line by line:

1. Only the first and last overlapping zero blocks can be cut by the query edges; every block in between is complete.
2. pair[t] for a + 1 ≤ t ≤ b − 2 involves only complete blocks, so the sparse table answers them in O(1).
3. The trade happens inside the substring, but the count is of 1s in the whole string, which is why ones is global.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Query covering no zeros.
• Query cutting both edge blocks.
• Exactly two blocks in the query.

Complexity: O(n log n + q log n) time, O(n log n) space.

Problem: Choose k distinct subarrays maximising the sum of their (max − min) values.

Solve it on LeetCode ↗

Constraints: 1 ≤ n == nums.length ≤ 5 * 10⁴ · 0 ≤ nums[i] ≤ 10⁹ · 1 ≤ k ≤ min(10⁵, n * (n + 1) / 2)

From brute force to the pattern: All subarrays sorted: O(n² log n). Heap merge: O((n + k) log n).

Spot it: Take the k largest subarray values. For a fixed left end, the value never decreases as r grows, so the largest is at r = n − 1. A max-heap merges these sorted lists (k-way merge), and sparse tables give each range max/min in O(1).

Why not another pattern? Listing all n²/2 subarray values is too many for n = 5·10⁴.

Approach:

1. Sparse tables for range max and min.
2. Push (value(l, n − 1), l, n − 1) for every l.
3. Pop k times; add the value; if r > l, push (value(l, r − 1), l, r − 1).

import heapq

class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        n = len(nums)
        hi_t, lo_t = [nums[:]], [nums[:]]  # sparse tables for range max / min
        j = 1
        while (1 << j) <= n:
            half = 1 << (j - 1)
            hi_t.append([max(hi_t[-1][i], hi_t[-1][i + half]) for i in range(n - (1 << j) + 1)])
            lo_t.append([min(lo_t[-1][i], lo_t[-1][i + half]) for i in range(n - (1 << j) + 1)])
            j += 1

        def value(l, r):
            j = (r - l + 1).bit_length() - 1
            top = max(hi_t[j][l], hi_t[j][r - (1 << j) + 1])  # two overlapping blocks cover [l, r]
            low = min(lo_t[j][l], lo_t[j][r - (1 << j) + 1])
            return top - low

        heap = [(-value(l, n - 1), l, n - 1) for l in range(n)]  # best subarray for each left end
        heapq.heapify(heap)
        total = 0
        for _ in range(k):
            neg, l, r = heapq.heappop(heap)
            total -= neg
            if r > l:
                heapq.heappush(heap, (-value(l, r - 1), l, r - 1))  # next best with the same left end
        return total

What the code is doing, line by line:

1. Shrinking a subarray can only lower its max and raise its min, so for each l the values are sorted by r descending.
2. The heap always holds the next-best candidate of every left end: a k-way merge of sorted lists.
3. A sparse table answers a range max/min with two overlapping power-of-two blocks.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k equal to the number of subarrays.
• All equal values (every value 0).
• n = 1.

Complexity: O(n log n + k log n) time, O(n log n) space.

Problem: After each point update, does some non-empty subsequence of length < n have gcd exactly p? Count the queries where it does.

Solve it on LeetCode ↗

Constraints: 2 ≤ n == nums.length ≤ 5 * 10⁴ · 1 ≤ nums[i] ≤ 5 * 10⁴ · 1 ≤ queries.length ≤ 5 * 10⁴ · queries[i] = [indi, vali] · 1 ≤ vali, p ≤ 5 * 10⁴ · 0 ≤ indi ≤ n - 1

From brute force to the pattern: Recomputing per query is O(n · q); the segment tree is O(log n) per query (plus a tiny check for n < 8).

Spot it: Only multiples of p can be in such a subsequence, and the best candidate is all of them: their gcd must be p. Keep that gcd under updates with a segment tree (non-multiples stored as 0, the gcd identity). If every element is a multiple, a proper subset with gcd p still exists when n ≥ 8 (numbers ≤ 5·10⁴ have at most 6 prime factors); for small n check each removal directly.

Why not another pattern? Recomputing gcds over the array per query is O(n · q).

Approach:

1. Leaf i holds nums[i] if p divides it, else 0; internal nodes hold the gcd.
2. Per query: update the leaf and the count of multiples. Let G = root gcd.
3. Good if G == p and (some element isn't a multiple, or n ≥ 8, or removing one element keeps gcd p).

from math import gcd

class Solution:
    def countGoodSubseq(self, nums: List[int], p: int, queries: List[List[int]]) -> int:
        n = len(nums)
        size = 1
        while size < n:
            size *= 2
        tree = [0] * (2 * size)  # gcd of multiples of p; 0 is the identity

        def put(i, value):
            i += size
            tree[i] = value if value % p == 0 else 0
            i //= 2
            while i:
                tree[i] = gcd(tree[2 * i], tree[2 * i + 1])
                i //= 2

        multiples = 0
        for i, v in enumerate(nums):
            put(i, v)
            multiples += v % p == 0
        good = 0
        for idx, val in queries:
            multiples += (val % p == 0) - (nums[idx] % p == 0)
            nums[idx] = val
            put(idx, val)
            if tree[1] != p:
                continue  # even all multiples together don't have gcd exactly p
            if multiples < n or n >= 8:
                good += 1  # all multiples form a proper subsequence (or a small proper subset exists)
                continue
            for skip in range(n):  # tiny n: try leaving one element out
                g = 0
                for j in range(n):
                    if j != skip:
                        g = gcd(g, nums[j])
                if g == p:
                    good += 1
                    break
        return good

What the code is doing, line by line:

1. A subsequence with gcd exactly p uses only multiples of p; adding more multiples can only lower the gcd toward their total gcd, so the total gcd must be p.
2. If some element isn't a multiple, "all multiples" is already shorter than n.
3. If all are multiples with gcd p, the values divided by p have gcd 1; one element plus one counterexample per prime factor (at most 6) gives a gcd-1 subset of at most 7 elements, so n ≥ 8 always works.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No multiples of p.
• All elements are multiples (needs a proper subset).
• p itself in the array.

Complexity: O((n + q) log n · log V) time, O(n) space.