前缀和与区间

def range_add(n: int, updates: list[tuple[int, int, int]]) -> list[int]:
    """n zeros, then each (l, r, v) adds v to positions l..r (LC 370)."""
    diff = [0] * (n + 1)  # diff[i] = a[i] - a[i - 1]; the extra slot takes r + 1 = n
    for l, r, v in updates:
        diff[l] += v
        diff[r + 1] -= v  # the change stops after r
    res, run = [], 0
    for i in range(n):
        run += diff[i]  # prefix sums of the differences rebuild the array
        res.append(run)
    return res

// n zeros, then each {l, r, v} adds v to positions l..r (LC 370).
vector<long long> rangeAdd(int n, const vector<array<int, 3>>& updates) {
    vector<long long> diff(n + 1, 0);  // diff[i] = a[i] - a[i - 1]; the extra slot takes r + 1 = n
    for (auto [l, r, v] : updates) {
        diff[l] += v;
        diff[r + 1] -= v;  // the change stops after r
    }
    vector<long long> res(n);
    long long run = 0;
    for (int i = 0; i < n; i++) res[i] = run += diff[i];  // prefix sums rebuild the array
    return res;
}

class Solution {
    // n zeros, then each {l, r, v} adds v to positions l..r (LC 370).
    long[] rangeAdd(int n, int[][] updates) {
        long[] diff = new long[n + 1]; // diff[i] = a[i] - a[i - 1]; the extra slot takes r + 1 = n
        for (int[] u : updates) {
            diff[u[0]] += u[2];
            diff[u[1] + 1] -= u[2]; // the change stops after r
        }
        long[] res = new long[n];
        long run = 0;
        for (int i = 0; i < n; i++) res[i] = run += diff[i]; // prefix sums rebuild the array
        return res;
    }
}

// rangeAdd starts from n zeros; each {l, r, v} adds v to positions l..r (LC 370).
func rangeAdd(n int, updates [][3]int) []int {
	diff := make([]int, n+1) // diff[i] = a[i] - a[i-1]; the extra slot takes r + 1 = n
	for _, u := range updates {
		diff[u[0]] += u[2]
		diff[u[1]+1] -= u[2] // the change stops after r
	}
	res := make([]int, n)
	run := 0
	for i := 0; i < n; i++ {
		run += diff[i] // prefix sums of the differences rebuild the array
		res[i] = run
	}
	return res
}

class Matrix2D:
    """Sum of any sub-rectangle in O(1) after O(rows × cols) setup (LC 304)."""

    def __init__(self, grid: list[list[int]]):
        rows, cols = len(grid), len(grid[0])
        # pre[r][c]: sum of the top-left r × c block; row 0 and column 0 stay zero
        self.pre = [[0] * (cols + 1) for _ in range(rows + 1)]
        for r in range(rows):
            for c in range(cols):
                self.pre[r + 1][c + 1] = self.pre[r][c + 1] + self.pre[r + 1][c] - self.pre[r][c] + grid[r][c]

    def sum(self, r1: int, c1: int, r2: int, c2: int) -> int:
        """Corners (r1, c1) and (r2, c2), both inclusive."""
        p = self.pre
        return p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1]

// Sum of any sub-rectangle in O(1) after O(rows × cols) setup (LC 304).
class Matrix2D {
    vector<vector<long long>> pre;  // pre[r][c]: sum of the top-left r × c block

public:
    explicit Matrix2D(const vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        pre.assign(rows + 1, vector<long long>(cols + 1, 0));  // row 0 and column 0 stay zero
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++) pre[r + 1][c + 1] = pre[r][c + 1] + pre[r + 1][c] - pre[r][c] + grid[r][c];
    }

    // Corners (r1, c1) and (r2, c2), both inclusive.
    long long sum(int r1, int c1, int r2, int c2) const {
        return pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1];
    }
};

// Sum of any sub-rectangle in O(1) after O(rows × cols) setup (LC 304).
class Matrix2D {
    private final long[][] pre; // pre[r][c]: sum of the top-left r × c block

    Matrix2D(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        pre = new long[rows + 1][cols + 1]; // row 0 and column 0 stay zero
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++) pre[r + 1][c + 1] = pre[r][c + 1] + pre[r + 1][c] - pre[r][c] + grid[r][c];
    }

    // Corners (r1, c1) and (r2, c2), both inclusive.
    long sum(int r1, int c1, int r2, int c2) {
        return pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1];
    }
}

// Matrix2D answers the sum of any sub-rectangle in O(1) after O(rows × cols) setup (LC 304).
type Matrix2D struct {
	pre [][]int // pre[r][c]: sum of the top-left r × c block
}

func NewMatrix2D(grid [][]int) *Matrix2D {
	rows, cols := len(grid), len(grid[0])
	pre := make([][]int, rows+1) // row 0 and column 0 stay zero
	for r := range pre {
		pre[r] = make([]int, cols+1)
	}
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			pre[r+1][c+1] = pre[r][c+1] + pre[r+1][c] - pre[r][c] + grid[r][c]
		}
	}
	return &Matrix2D{pre}
}

// Sum takes corners (r1, c1) and (r2, c2), both inclusive.
func (m *Matrix2D) Sum(r1, c1, r2, c2 int) int {
	p := m.pre
	return p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1]
}

def merge(intervals: list[list[int]]) -> list[list[int]]:
    """Union of closed intervals, by start; touching ones such as [1, 2] and [2, 3] merge."""
    res: list[list[int]] = []
    for start, end in sorted(intervals):
        if res and start <= res[-1][1]:  # overlaps the last merged interval
            res[-1][1] = max(res[-1][1], end)
        else:
            res.append([start, end])
    return res

// Union of closed intervals, by start; touching ones such as [1, 2] and [2, 3] merge.
vector<pair<int, int>> mergeIntervals(vector<pair<int, int>> intervals) {
    sort(intervals.begin(), intervals.end());
    vector<pair<int, int>> res;
    for (auto [start, end] : intervals) {
        if (!res.empty() && start <= res.back().second)  // overlaps the last merged interval
            res.back().second = max(res.back().second, end);
        else
            res.push_back({start, end});
    }
    return res;
}

class Solution {
    // Union of closed intervals, by start; touching ones such as [1, 2] and [2, 3] merge.
    List<int[]> merge(int[][] intervals) {
        int[][] sorted = intervals.clone();
        Arrays.sort(sorted, Comparator.comparingInt(iv -> iv[0]));
        List<int[]> res = new ArrayList<>();
        for (int[] iv : sorted) {
            int[] last = res.isEmpty() ? null : res.get(res.size() - 1);
            if (last != null && iv[0] <= last[1]) last[1] = Math.max(last[1], iv[1]); // overlaps the last merged interval
            else res.add(new int[] {iv[0], iv[1]});
        }
        return res;
    }
}

import "sort"

// merge returns the union of closed intervals, by start; touching ones such as [1, 2] and [2, 3] merge.
func merge(intervals [][2]int) [][2]int {
	sorted := append([][2]int(nil), intervals...)
	sort.Slice(sorted, func(i, j int) bool { return sorted[i][0] < sorted[j][0] })
	var res [][2]int
	for _, iv := range sorted {
		if n := len(res); n > 0 && iv[0] <= res[n-1][1] { // overlaps the last merged interval
			res[n-1][1] = max(res[n-1][1], iv[1])
		} else {
			res = append(res, iv)
		}
	}
	return res
}