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
// 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