差分陣列

def difference_array_template(nums, updates):
    """
    Universal template for difference array problems
    nums: original array
    updates: list of [start, end, value] operations
    """
    n = len(nums)
    # Build difference array
    diff = [0] * n
    diff[0] = nums[0]
    for i in range(1, n):
        diff[i] = nums[i] - nums[i-1]
    
    # Apply range updates in O(1) each
    for start, end, val in updates:
        diff[start] += val
        if end + 1 < n:
            diff[end + 1] -= val
    
    # Reconstruct final array
    result = [0] * n
    result[0] = diff[0]
    for i in range(1, n):
        result[i] = result[i-1] + diff[i]
    
    return result

class DifferenceArray:
    def __init__(self, nums):
        """Initialize difference array from original array"""
        self.n = len(nums)
        self.diff = [0] * self.n
        
        # Build difference array
        self.diff[0] = nums[0]
        for i in range(1, self.n):
            self.diff[i] = nums[i] - nums[i-1]
    
    def update(self, start, end, val):
        """Add val to all elements in range [start, end] in O(1)"""
        self.diff[start] += val
        if end + 1 < self.n:
            self.diff[end + 1] -= val
    
    def get_result(self):
        """Reconstruct the final array in O(n)"""
        result = [0] * self.n
        result[0] = self.diff[0]
        for i in range(1, self.n):
            result[i] = result[i-1] + self.diff[i]
        return result

def check_resource_allocation(intervals, capacity, resource_field=2):
    """
    Check if resource allocation is valid
    intervals: [[start, end, resource_needed], ...]
    capacity: maximum available resource
    """
    # Find the range of positions
    max_pos = max(interval[1] for interval in intervals) + 1
    diff = [0] * max_pos
    
    # Apply all resource allocations
    for interval in intervals:
        start, end, resource = interval[0], interval[1], interval[resource_field]
        diff[start] += resource
        if end + 1 < max_pos:
            diff[end + 1] -= resource
    
    # Check if any position exceeds capacity
    current = 0
    for i in range(max_pos):
        current += diff[i]
        if current > capacity:
            return False
    
    return True

def process_events(events):
    """
    Process events on a timeline
    events: [[start_time, end_time, value], ...]
    Returns: timeline with accumulated values
    """
    if not events:
        return []
    
    # Create timeline
    max_time = max(e[1] for e in events) + 1
    timeline = [0] * max_time
    
    # Process each event
    for start, end, value in events:
        timeline[start] += value
        if end + 1 < max_time:
            timeline[end + 1] -= value
    
    # Calculate prefix sum to get actual values
    for i in range(1, max_time):
        timeline[i] += timeline[i-1]
    
    return timeline

class DifferenceArray2D:
    def __init__(self, matrix):
        """Initialize 2D difference array"""
        self.m, self.n = len(matrix), len(matrix[0])
        self.diff = [[0] * self.n for _ in range(self.m)]
        
        # Build 2D difference array
        for i in range(self.m):
            for j in range(self.n):
                self.diff[i][j] = matrix[i][j]
                if i > 0:
                    self.diff[i][j] -= matrix[i-1][j]
                if j > 0:
                    self.diff[i][j] -= matrix[i][j-1]
                if i > 0 and j > 0:
                    self.diff[i][j] += matrix[i-1][j-1]
    
    def update(self, r1, c1, r2, c2, val):
        """Add val to all elements in rectangle [r1,c1] to [r2,c2]"""
        self.diff[r1][c1] += val
        if r2 + 1 < self.m:
            self.diff[r2 + 1][c1] -= val
        if c2 + 1 < self.n:
            self.diff[r1][c2 + 1] -= val
        if r2 + 1 < self.m and c2 + 1 < self.n:
            self.diff[r2 + 1][c2 + 1] += val
    
    def get_result(self):
        """Reconstruct the final 2D array"""
        result = [[0] * self.n for _ in range(self.m)]
        
        for i in range(self.m):
            for j in range(self.n):
                result[i][j] = self.diff[i][j]
                if i > 0:
                    result[i][j] += result[i-1][j]
                if j > 0:
                    result[i][j] += result[i][j-1]
                if i > 0 and j > 0:
                    result[i][j] -= result[i-1][j-1]
        
        return result

def difference_array_compressed(updates):
    """
    Handle large coordinate space with compression
    updates: [[start, end, value], ...]
    """
    # Collect all unique points
    points = set()
    for start, end, _ in updates:
        points.add(start)
        points.add(end + 1)
    
    # Sort and create mapping
    sorted_points = sorted(points)
    point_to_idx = {p: i for i, p in enumerate(sorted_points)}
    
    # Apply updates on compressed coordinates
    n = len(sorted_points)
    diff = [0] * n
    
    for start, end, val in updates:
        start_idx = point_to_idx[start]
        end_idx = point_to_idx.get(end + 1, n)
        diff[start_idx] += val
        if end_idx < n:
            diff[end_idx] -= val
    
    # Calculate values at each point
    for i in range(1, n):
        diff[i] += diff[i-1]
    
    # Return results with original coordinates
    result = {}
    for i, point in enumerate(sorted_points[:-1]):  # Exclude the last dummy point
        if diff[i] != 0:
            result[point] = diff[i]
    
    return result

# python — LC 3964 Minimum Lights to Illuminate a Road
#
# core idea (3 phases):
#   1. DIFF ARRAY  -> mark every range an existing bulb covers in O(1) each
#   2. PREFIX SUM  -> turn diff into a `covered[i]` map (0 == dark spot)
#   3. GREEDY      -> walk left->right; at each dark spot drop 1 new bulb and
#                     jump ahead 3 (a new bulb at i+1 lights i, i+1, i+2)
#
# time  = O(n)   diff build + prefix sum + single greedy pass
# space = O(n)   difference array + coverage map
def minLights(lights):
    n = len(lights)

    # 1) difference array (size n+1 so `right+1` never overflows)
    diff = [0] * (n + 1)
    for i, v in enumerate(lights):
        if v > 0:
            left  = max(0, i - v)
            right = min(n - 1, i + v)
            diff[left]      += 1        # +1 where coverage starts
            diff[right + 1] -= 1        # -1 right AFTER it ends

    # 2) prefix sum -> covered[i] > 0 means position i is already lit
    covered = [0] * n
    running = 0
    for i in range(n):
        running += diff[i]
        covered[i] = running

    # 3) greedy fill of the dark gaps
    ans = 0
    i = 0
    while i < n:
        if covered[i] == 0:             # dark spot found
            ans += 1
            # best move: put bulb at i+1 -> covers i, i+1, i+2 -> jump 3
            i += 3
        else:
            i += 1                      # already lit -> next position
    return ans

// java
// LC 699 - Falling Squares
// IDEA: coordinate-compress the 2n endpoints, then a segment tree with a LAZY ASSIGN tag
//       supports "max over [l,r]" and "set [l,r] = h" in O(log n) each.
//       Per square: h = query(l, r) + size; assign(l, r, h); answer = running max.
// time = O(n log n), space = O(n)
class Solution {
    private int[] mx, lz;   // mx = max height in node's range, lz = pending "assign" tag (0 = none)

    public List<Integer> fallingSquares(int[][] positions) {
        // 1) coordinate compression of all endpoints
        TreeSet<Integer> set = new TreeSet<>();
        for (int[] p : positions) { set.add(p[0]); set.add(p[0] + p[1]); }
        List<Integer> xs = new ArrayList<>(set);
        Map<Integer, Integer> idx = new HashMap<>();
        for (int i = 0; i < xs.size(); i++) idx.put(xs.get(i), i);
        int m = xs.size() - 1;                 // # of elementary segments

        mx = new int[4 * Math.max(m, 1)];
        lz = new int[4 * Math.max(m, 1)];

        List<Integer> res = new ArrayList<>();
        int best = 0;
        for (int[] p : positions) {
            // NOTE !!! square covers [l, l+size) -> closed leaf range [a, b]
            int a = idx.get(p[0]);
            int b = idx.get(p[0] + p[1]) - 1;
            int cur = query(1, 0, m - 1, a, b);        // tallest thing already under it
            update(1, 0, m - 1, a, b, cur + p[1]);     // it lands ON TOP -> assign, not add
            best = Math.max(best, cur + p[1]);
            res.add(best);
        }
        return res;
    }

    // push the pending assign tag down to both children
    private void push(int node) {
        if (lz[node] != 0) {
            for (int c = 2 * node; c <= 2 * node + 1; c++) {
                mx[c] = lz[node];
                lz[c] = lz[node];
            }
            lz[node] = 0;
        }
    }

    private void update(int node, int lo, int hi, int l, int r, int val) {
        if (r < lo || hi < l) return;                       // disjoint
        if (l <= lo && hi <= r) {                           // fully covered -> tag & stop
            mx[node] = val; lz[node] = val; return;
        }
        push(node);
        int mid = (lo + hi) >>> 1;
        update(2 * node, lo, mid, l, r, val);
        update(2 * node + 1, mid + 1, hi, l, r, val);
        mx[node] = Math.max(mx[2 * node], mx[2 * node + 1]);
    }

    private int query(int node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) return 0;
        if (l <= lo && hi <= r) return mx[node];
        push(node);
        int mid = (lo + hi) >>> 1;
        return Math.max(query(2 * node, lo, mid, l, r),
                        query(2 * node + 1, mid + 1, hi, l, r));
    }
}

# python
# LC 699 - Falling Squares
# IDEA: same as java — compress endpoints, segment tree with a lazy ASSIGN tag.
#       max is not invertible, so the diff-array "+val at l, -val at r+1" trick does not apply.
# time = O(n log n), space = O(n)
class Solution(object):
    def fallingSquares(self, positions):
        # 1) coordinate compression
        xs = sorted({x for l, s in positions for x in (l, l + s)})
        idx = {x: i for i, x in enumerate(xs)}
        m = len(xs) - 1                       # # of elementary segments

        size = 4 * max(m, 1)
        mx = [0] * size                       # max height in node's range
        lz = [0] * size                       # pending assign tag (0 = none)

        def push(node):
            if lz[node]:
                for c in (2 * node, 2 * node + 1):
                    mx[c] = lz[node]
                    lz[c] = lz[node]
                lz[node] = 0

        def update(node, lo, hi, l, r, val):
            if r < lo or hi < l:              # disjoint
                return
            if l <= lo and hi <= r:           # fully covered -> tag & stop
                mx[node] = val
                lz[node] = val
                return
            push(node)
            mid = (lo + hi) // 2
            update(2 * node, lo, mid, l, r, val)
            update(2 * node + 1, mid + 1, hi, l, r, val)
            mx[node] = max(mx[2 * node], mx[2 * node + 1])

        def query(node, lo, hi, l, r):
            if r < lo or hi < l:
                return 0
            if l <= lo and hi <= r:
                return mx[node]
            push(node)
            mid = (lo + hi) // 2
            return max(query(2 * node, lo, mid, l, r),
                       query(2 * node + 1, mid + 1, hi, l, r))

        res, best = [], 0
        for l, s in positions:
            # square covers [l, l+s) -> closed leaf range [a, b]
            a, b = idx[l], idx[l + s] - 1
            cur = query(1, 0, m - 1, a, b)    # tallest thing already under it
            update(1, 0, m - 1, a, b, cur + s)  # lands ON TOP -> assign
            best = max(best, cur + s)
            res.append(best)
        return res

// java
// https://labuladong.online/algo/data-structure/diff-array/

// 差分数组工具类
// V1
class Difference {
    // 差分数组
    private int[] diff;
    
    // 输入一个初始数组，区间操作将在这个数组上进行
    public Difference(int[] nums) {
        assert nums.length > 0;
        diff = new int[nums.length];
        // 根据初始数组构造差分数组
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    // 给闭区间 [i, j] 增加 val（可以是负数）
    public void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.length) {
            diff[j + 1] -= val;
        }
    }

    // 返回结果数组
    public int[] result() {
        int[] res = new int[diff.length];
        // 根据差分数组构造结果数组
        res[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }
}

// V2
// https://github.com/yennanliu/CS_basics/blob/master/leetcode_java/src/main/java/AlgorithmJava/DifferenceArray.java


// method
public int[] getDifferenceArray(int[][] input, int n) {

/** LC 1109. Corporate Flight Bookings input : [start, end, seats]
 *
 *  NOTE !!!
 *
 *   in java, index start from 0;
 *   but in LC 1109, index start from 1
 *
 */
int[] tmp = new int[n + 1];
for (int[] x : input) {
  int start = x[0];
  int end = x[1];
  int seats = x[2];

  // add
  tmp[start] += seats;

  // subtract
  if (end + 1 <= n) {
    tmp[end + 1] -= seats;
  }
}

for (int i = 1; i < tmp.length; i++) {
  //tmp[i] = tmp[i - 1] + tmp[i];
    tmp[i] += tmp[i - 1];
}

return Arrays.copyOfRange(tmp, 1, n+1);
}

// java
// LC 370


// V0
// IDEA : DIFFERENCE ARRAY
public static int[] getModifiedArray(int length, int[][] updates) {

int[] tmp = new int[length + 1]; // or new int[length]; both works
for (int[] x : updates) {
  int start = x[0];
  int end = x[1];
  int amount = x[2];

  // add
  tmp[start] += amount;

  // subtract (remove the "adding affect" on "NEXT" element)
  /**
   * NOTE !!!
   *
   * <p>we remove the "adding affect" on NEXT element (e.g. end + 1)
   */
  if (end + 1 < length) { // NOTE !!! use `end + 1`
    tmp[end + 1] -= amount;
  }
}

// prepare final result
for (int i = 1; i < tmp.length; i++) {
  tmp[i] += tmp[i - 1];
}

return Arrays.copyOfRange(tmp, 0, length); // return the sub array between 0, lengh index
}

// V1
class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        // nums 初始化为全 0
        int[] nums = new int[length];
        // 构造差分解法
        Difference df = new Difference(nums);
        
        for (int[] update : updates) {
            int i = update[0];
            int j = update[1];
            int val = update[2];
            df.increment(i, j, val);
        }
        
        return df.result();
    }
}

// java
// LC 1109

// V1
class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        // nums 初始化为全 0
        int[] nums = new int[n];
        // 构造差分解法
        Difference df = new Difference(nums);

        for (int[] booking : bookings) {
            // 注意转成数组索引要减一哦
            int i = booking[0] - 1;
            int j = booking[1] - 1;
            int val = booking[2];
            // 对区间 nums[i..j] 增加 val
            df.increment(i, j, val);
        }
        // 返回最终的结果数组
        return df.result();
    }
}

// java
// LC 1094
// https://leetcode.com/problems/car-pooling/description/

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        // 最多有 1001 个车站
        int[] nums = new int[1001];

        // 构造差分解法
        Difference df = new Difference(nums);

        for (int[] trip : trips) {
            // 乘客数量
            int val = trip[0];

            // 第 trip[1] 站乘客上车
            int i = trip[1];

            // 第 trip[2] 站乘客已经下车，
            // 即乘客在车上的区间是 [trip[1], trip[2] - 1]
            int j = trip[2] - 1;

            // 进行区间操作
            df.increment(i, j, val);
        }

        int[] res = df.result();

        // 客车自始至终都不应该超载
        for (int i = 0; i < res.length; i++) {
            if (capacity < res[i]) {
                return false;
            }
        }
        return true;
    }
}

# python
# LC 3964
class Solution(object):
    def minLights(self, lights):
        n = len(lights)

        # 1) difference array (size n+1 so right+1 is always safe)
        diff = [0] * (n + 1)
        for i, v in enumerate(lights):
            if v > 0:
                left  = max(0, i - v)
                right = min(n - 1, i + v)
                diff[left]      += 1
                diff[right + 1] -= 1

        # 2) prefix sum -> coverage map
        covered = [0] * n
        run = 0
        for i in range(n):
            run += diff[i]
            covered[i] = run

        # 3) greedy fill
        ans = 0
        i = 0
        while i < n:
            if covered[i] == 0:
                ans += 1
                i += 3          # new bulb at i+1 covers i, i+1, i+2
            else:
                i += 1
        return ans

# python — compact variant: count dark runs, ceil-divide by bulb width 3
class Solution(object):
    def minLights(self, lights):
        n = len(lights)
        diff = [0] * (n + 1)
        for i, v in enumerate(lights):
            if v > 0:
                diff[max(0, i - v)]          += 1
                diff[min(n - 1, i + v) + 1]  -= 1

        cover = run = ans = 0
        for i in range(n):
            cover += diff[i]
            if cover == 0:
                run += 1                     # extend current dark run
            else:
                ans += (run + 2) // 3        # ceil(run / 3) bulbs for the run
                run = 0
        ans += (run + 2) // 3                # flush trailing dark run
        return ans

Difference Array Problem Analysis Flowchart:

1. Does the problem involve range updates?
   ├── YES → Check update pattern
   │   ├── Multiple ranges need same update? → Use Difference Array
   │   ├── Single element updates? → Use direct array
   │   └── Need immediate query results? → Consider Segment Tree
   └── NO → Not a difference array problem

2. What type of range operation?
   ├── Add/Subtract constant to range → Basic Difference Array (Template 1)
   ├── Track resource usage → Resource Allocation (Template 2)
   ├── Timeline/Event processing → Event Timeline (Template 3)
   └── 2D matrix updates → 2D Difference Array (Template 4)

3. Space/Time Trade-offs:
   ├── Large coordinate space? → Use Coordinate Compression (Template 5)
   ├── Many queries between updates? → Consider Lazy Propagation
   └── Only final result needed? → Basic Difference Array

4. Special Considerations:
   ├── Online vs Offline → Difference array is offline
   ├── Need range queries? → Combine with Prefix Sum
   └── Overlapping intervals? → Check maximum overlap

# To add val to range [start, end]:
diff[start] += val
if end + 1 < n:
    diff[end + 1] -= val

# If passengers get off at station x, they're on board [start, x-1]
# If event ends at time t, it's active [start, t]
# Be careful with inclusive/exclusive boundaries!

# Car pooling example:
for passengers, pickup, dropoff in trips:
    diff[pickup] += passengers
    diff[dropoff] -= passengers  # Not dropoff-1!

def max_concurrent(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))   # Start event
        events.append((end + 1, -1)) # End event
    
    events.sort()
    max_concurrent = current = 0
    
    for time, delta in events:
        current += delta
        max_concurrent = max(max_concurrent, current)
    
    return max_concurrent

// Java Difference Array Class
class Difference {
    private int[] diff;
    
    public Difference(int[] nums) {
        diff = new int[nums.length];
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i-1];
        }
    }
    
    public void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.length) {
            diff[j + 1] -= val;
        }
    }
    
    public int[] result() {
        int[] res = new int[diff.length];
        res[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            res[i] = res[i-1] + diff[i];
        }
        return res;
    }
}

# Python class implementation
class DifferenceArray:
    def __init__(self, nums):
        self.n = len(nums)
        self.diff = [0] * self.n
        if nums:
            self.diff[0] = nums[0]
            for i in range(1, self.n):
                self.diff[i] = nums[i] - nums[i-1]
    
    def update(self, start, end, val):
        self.diff[start] += val
        if end + 1 < self.n:
            self.diff[end + 1] -= val
    
    def get_result(self):
        result = [self.diff[0]]
        for i in range(1, self.n):
            result.append(result[-1] + self.diff[i])
        return result