Prefix Sum Patterns — Comprehensive Guide

def build_prefix(a):
    n = len(a)
    pre = [0] * (n + 1)
    for i in range(n):
        pre[i + 1] = pre[i] + a[i]
    return pre

def range_sum(pre, l, r):
    """Sum of a[l..r] inclusive."""
    return pre[r + 1] - pre[l]

# Python shortcut using itertools
from itertools import accumulate
def build_prefix_v2(a):
    return [0] + list(accumulate(a))

def build_2d_prefix(grid):
    R, C = len(grid), len(grid[0])
    pre = [[0] * (C + 1) for _ in range(R + 1)]
    for i in range(R):
        for j in range(C):
            pre[i+1][j+1] = (grid[i][j]
                             + pre[i][j+1]
                             + pre[i+1][j]
                             - pre[i][j])
    return pre

def rect_sum(pre, r1, c1, r2, c2):
    """Sum of grid[r1..r2][c1..c2] inclusive."""
    return (pre[r2+1][c2+1]
            - pre[r1][c2+1]
            - pre[r2+1][c1]
            + pre[r1][c1])

from collections import defaultdict

def subarray_sum_count(a, k):
    """Count subarrays with sum exactly k."""
    count = defaultdict(int)
    count[0] = 1  # empty prefix
    current_sum = 0
    result = 0

    for x in a:
        current_sum += x
        # How many prefixes had sum = current_sum - k?
        result += count[current_sum - k]
        count[current_sum] += 1

    return result

def longest_subarray_sum_k(a, k):
    """Find length of longest subarray with sum k."""
    first_occurrence = {0: -1}  # prefix_sum -> earliest index
    current_sum = 0
    best = 0

    for i, x in enumerate(a):
        current_sum += x
        if current_sum - k in first_occurrence:
            best = max(best, i - first_occurrence[current_sum - k])
        # Only store first occurrence (we want longest)
        if current_sum not in first_occurrence:
            first_occurrence[current_sum] = i

    return best

def count_sum_in_range(a, lo, hi):
    """Count subarrays with sum in [lo, hi]."""
    # count(sum ≤ hi) - count(sum ≤ lo - 1)
    return _count_at_most(a, hi) - _count_at_most(a, lo - 1)

def _count_at_most(a, target):
    """Count subarrays with sum ≤ target. Uses sorted container or merge sort."""
    # For general arrays (with negatives), this requires more advanced DS
    # For non-negative arrays, sliding window works
    pass

def subarrays_divisible_by_k(a, k):
    """Count subarrays with sum divisible by k."""
    count = [0] * k
    count[0] = 1  # empty prefix has sum 0, remainder 0
    current_sum = 0
    result = 0

    for x in a:
        current_sum += x
        rem = current_sum % k
        # In Python, % always returns non-negative for positive k
        result += count[rem]
        count[rem] += 1

    return result

def range_add(diff, l, r, v):
    """Add v to all elements in [l, r] inclusive."""
    diff[l] += v
    if r + 1 < len(diff):
        diff[r + 1] -= v

def reconstruct(diff):
    """Convert difference array back to original array."""
    a = [0] * len(diff)
    a[0] = diff[0]
    for i in range(1, len(diff)):
        a[i] = a[i - 1] + diff[i]
    return a

# Usage
n = 6
diff = [0] * n
range_add(diff, 1, 4, 3)    # add 3 to [1..4]
range_add(diff, 0, 2, 2)    # add 2 to [0..2]
range_add(diff, 2, 5, -1)   # add -1 to [2..5]
result = reconstruct(diff)   # [2, 5, 4, 2, 2, -1]

def range_add_2d(diff, r1, c1, r2, c2, v):
    """Add v to all cells in rectangle (r1,c1)-(r2,c2) inclusive."""
    diff[r1][c1] += v
    if c2 + 1 < len(diff[0]):
        diff[r1][c2 + 1] -= v
    if r2 + 1 < len(diff):
        diff[r2 + 1][c1] -= v
    if r2 + 1 < len(diff) and c2 + 1 < len(diff[0]):
        diff[r2 + 1][c2 + 1] += v

def reconstruct_2d(diff):
    """Convert 2D difference array to original grid."""
    R, C = len(diff), len(diff[0])
    # Row-wise prefix sum
    for i in range(R):
        for j in range(1, C):
            diff[i][j] += diff[i][j - 1]
    # Column-wise prefix sum
    for j in range(C):
        for i in range(1, R):
            diff[i][j] += diff[i - 1][j]
    return diff

def build_prefix_xor(a):
    n = len(a)
    pre = [0] * (n + 1)
    for i in range(n):
        pre[i + 1] = pre[i] ^ a[i]
    return pre

def range_xor(pre, l, r):
    """XOR of a[l..r] inclusive."""
    return pre[r + 1] ^ pre[l]

from collections import defaultdict

def count_subarrays_xor_k(a, k):
    """Count subarrays with XOR equal to k."""
    count = defaultdict(int)
    count[0] = 1
    current_xor = 0
    result = 0

    for x in a:
        current_xor ^= x
        # pre[j] ^ pre[i] = k  ⟺  pre[i] = pre[j] ^ k
        result += count[current_xor ^ k]
        count[current_xor] += 1

    return result

def product_except_self(a):
    n = len(a)
    result = [1] * n

    # Left pass: result[i] = product of a[0..i-1]
    left = 1
    for i in range(n):
        result[i] = left
        left *= a[i]

    # Right pass: multiply by product of a[i+1..n-1]
    right = 1
    for i in range(n - 1, -1, -1):
        result[i] *= right
        right *= a[i]

    return result

from math import gcd
from functools import reduce

def gcd_except_self(a):
    n = len(a)
    prefix_gcd = [0] * n
    suffix_gcd = [0] * n

    prefix_gcd[0] = a[0]
    for i in range(1, n):
        prefix_gcd[i] = gcd(prefix_gcd[i-1], a[i])

    suffix_gcd[n-1] = a[n-1]
    for i in range(n-2, -1, -1):
        suffix_gcd[i] = gcd(a[i], suffix_gcd[i+1])

    result = [0] * n
    for i in range(n):
        left = prefix_gcd[i-1] if i > 0 else 0
        right = suffix_gcd[i+1] if i < n-1 else 0
        if left == 0:
            result[i] = right
        elif right == 0:
            result[i] = left
        else:
            result[i] = gcd(left, right)
    return result

import sys
from collections import defaultdict
sys.setrecursionlimit(300000)

def solve_path_queries(n, edges, values, queries):
    """
    Given a tree with node values, answer:
    "What is the sum of values on path u → v?"
    Using depth prefix sums + LCA.
    """
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    # Precompute depth_sum[v] = sum of values from root to v
    LOG = 20
    depth = [0] * n
    depth_sum = [0] * n
    parent = [[-1] * n for _ in range(LOG)]

    # BFS to set up parent, depth, depth_sum
    from collections import deque
    visited = [False] * n
    queue = deque([0])
    visited[0] = True
    depth_sum[0] = values[0]

    while queue:
        u = queue.popleft()
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                parent[0][v] = u
                depth[v] = depth[u] + 1
                depth_sum[v] = depth_sum[u] + values[v]
                queue.append(v)

    # Build binary lifting table
    for k in range(1, LOG):
        for v in range(n):
            if parent[k-1][v] != -1:
                parent[k][v] = parent[k-1][parent[k-1][v]]

    def lca(u, v):
        if depth[u] < depth[v]:
            u, v = v, u
        diff = depth[u] - depth[v]
        for k in range(LOG):
            if (diff >> k) & 1:
                u = parent[k][u]
        if u == v:
            return u
        for k in range(LOG - 1, -1, -1):
            if parent[k][u] != parent[k][v]:
                u = parent[k][u]
                v = parent[k][v]
        return parent[0][u]

    results = []
    for u, v in queries:
        l = lca(u, v)
        # path sum = depth_sum[u] + depth_sum[v] - 2*depth_sum[l] + values[l]
        ans = depth_sum[u] + depth_sum[v] - 2 * depth_sum[l] + values[l]
        results.append(ans)
    return results

def count_paths_through_nodes(n, adj, paths):
    """
    Given paths [(u, v), ...], count how many paths pass through each node.
    Uses difference on tree technique.
    """
    # Setup LCA (assume already built as above)
    # ...

    diff = [0] * n
    for u, v in paths:
        l = lca(u, v)
        diff[u] += 1
        diff[v] += 1
        diff[l] -= 1
        p = parent[0][l]
        if p != -1:
            diff[p] -= 1

    # DFS to accumulate subtree sums
    answer = [0] * n
    def dfs(u, par):
        answer[u] = diff[u]
        for v in adj[u]:
            if v != par:
                dfs(v, u)
                answer[u] += answer[v]

    dfs(0, -1)
    return answer

from bisect import bisect_left

def min_subarray_with_sum_at_least(a, target):
    """
    Find shortest subarray with sum ≥ target.
    Assumes all elements non-negative.
    """
    n = len(a)
    pre = [0] * (n + 1)
    for i in range(n):
        pre[i + 1] = pre[i] + a[i]

    best = float('inf')
    for j in range(1, n + 1):
        # Need pre[j] - pre[i] ≥ target → pre[i] ≤ pre[j] - target
        # Find rightmost i with pre[i] ≤ pre[j] - target
        # Since pre is sorted (non-negative elements), use bisect
        threshold = pre[j] - target
        i = bisect_left(pre, threshold + 1, 0, j) - 1
        if i >= 0 and pre[j] - pre[i] >= target:
            best = min(best, j - i)

    return best if best != float('inf') else -1

from bisect import bisect_left, bisect_right

def count_subarrays_sum_in_range(a, lo, hi):
    """
    Count subarrays with sum in [lo, hi].
    Assumes all elements non-negative (prefix sums are sorted).
    """
    n = len(a)
    pre = [0] * (n + 1)
    for i in range(n):
        pre[i + 1] = pre[i] + a[i]

    count = 0
    for j in range(1, n + 1):
        # Need lo ≤ pre[j] - pre[i] ≤ hi
        # → pre[j] - hi ≤ pre[i] ≤ pre[j] - lo
        low_bound = pre[j] - hi
        high_bound = pre[j] - lo
        # Count i in [0, j) where low_bound ≤ pre[i] ≤ high_bound
        left = bisect_left(pre, low_bound, 0, j)
        right = bisect_right(pre, high_bound, 0, j)
        count += right - left

    return count

from sortedcontainers import SortedList

def count_subarrays_sum_in_range_general(a, lo, hi):
    """Works even with negative values."""
    sl = SortedList([0])  # prefix sums seen so far
    current_sum = 0
    count = 0

    for x in a:
        current_sum += x
        # Count previous prefix sums in [current_sum - hi, current_sum - lo]
        left = sl.bisect_left(current_sum - hi)
        right = sl.bisect_right(current_sum - lo)
        count += right - left
        sl.add(current_sum)

    return count

def sum_over_subsets(f, n_bits):
    """
    Compute sos[x] = sum of f[y] for all submasks y of x.
    n_bits: number of bits to consider.
    f: array of size 2^n_bits.
    """
    sos = f[:]  # copy
    for bit in range(n_bits):
        for mask in range(1 << n_bits):
            if mask & (1 << bit):
                sos[mask] += sos[mask ^ (1 << bit)]
    return sos

def mobius_inverse(sos, n_bits):
    """Inverse of sum_over_subsets."""
    f = sos[:]
    for bit in range(n_bits):
        for mask in range(1 << n_bits):
            if mask & (1 << bit):
                f[mask] -= f[mask ^ (1 << bit)]
    return f

def sum_over_supermasks(f, n_bits):
    sos = f[:]
    for bit in range(n_bits):
        for mask in range(1 << n_bits):
            if not (mask & (1 << bit)):  # bit NOT set
                sos[mask] += sos[mask | (1 << bit)]
    return sos

# Balance never goes negative
def can_complete_circuit(gas, cost):
    """Circular gas station problem."""
    n = len(gas)
    total = 0
    tank = 0
    start = 0
    for i in range(n):
        diff = gas[i] - cost[i]
        total += diff
        tank += diff
        if tank < 0:
            start = i + 1
            tank = 0
    return start if total >= 0 else -1

def range_count_zeros(a):
    """Build prefix count of zeros for range queries."""
    n = len(a)
    count_zeros = [0] * (n + 1)
    for i in range(n):
        count_zeros[i + 1] = count_zeros[i] + (1 if a[i] == 0 else 0)

    # Zeros in a[l..r] = count_zeros[r+1] - count_zeros[l]
    return count_zeros

def build_char_prefix(s):
    """Build prefix frequency for each character."""
    n = len(s)
    pre = [[0] * 26 for _ in range(n + 1)]
    for i in range(n):
        for c in range(26):
            pre[i + 1][c] = pre[i][c]
        pre[i + 1][ord(s[i]) - ord('a')] += 1
    return pre

def count_char_in_range(pre, l, r, ch):
    """Count occurrences of ch in s[l..r]."""
    c = ord(ch) - ord('a')
    return pre[r + 1][c] - pre[l][c]

def trapping_rain_water(height):
    """Classic problem: how much water can be trapped?"""
    n = len(height)
    if n == 0:
        return 0

    left_max = [0] * n
    right_max = [0] * n

    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i-1], height[i])

    right_max[n-1] = height[n-1]
    for i in range(n-2, -1, -1):
        right_max[i] = max(right_max[i+1], height[i])

    water = 0
    for i in range(n):
        water += min(left_max[i], right_max[i]) - height[i]
    return water

def max_overlapping_intervals(intervals, max_val):
    """Find maximum number of overlapping intervals."""
    diff = [0] * (max_val + 2)
    for start, end in intervals:
        diff[start] += 1
        diff[end + 1] -= 1

    # Prefix sum = count of active intervals at each point
    max_overlap = 0
    current = 0
    for i in range(max_val + 1):
        current += diff[i]
        max_overlap = max(max_overlap, current)
    return max_overlap

def subarray_with_sum(a, target):
    """Find subarray with exact sum (non-negative elements)."""
    current = 0
    left = 0
    for right in range(len(a)):
        current += a[right]
        while current > target and left <= right:
            current -= a[left]
            left += 1
        if current == target:
            return (left, right)
    return None