Overview

This problem is a typical Lazy Segment Tree problem that requires efficiently performing range updates and range sum queries.

Analysis

In this problem, operations to add water to flower beds (range updates) and operations to find the total amount of water in a given range of flower beds (range sum queries) are performed multiple times.

A naive approach would be to directly update the array and compute the sum for each operation, but in the worst case each operation takes \(O(N)\), resulting in an overall complexity of \(O(Q \cdot N)\), which will TLE given the constraints \(N, Q \leq 10^5\).

By using a “Lazy Segment Tree,” which can efficiently perform range updates and range queries, each operation can be processed in \(O(\log N)\).

Algorithm

The data structure used to solve this problem is the Lazy Segment Tree.

A Lazy Segment Tree has the following characteristics:

• Range value updates (e.g., adding \(v\) to a range)
• Range value queries (e.g., range sum)
• Both operations can be performed efficiently in \(O(\log N)\)

Main Roles of the Class

• tree: A regular segment tree that holds the sum of each interval
• lazy: An array for lazy evaluation that stores values to be uniformly added to an interval

Processing Flow

1. Build the segment tree from the initial data
2. For operation 1 (range update), call update(l, r, v) to add \(v\) to the interval \([l, r]\)
3. For operation 2 (range sum query), call query(l, r) and output the result

Internally, the _push function propagates lazy information to child nodes, ensuring that the information is always up to date.

Complexity

• Time complexity: \(O(Q \log N)\)
• Space complexity: \(O(N)\)

Each operation is \(O(\log N)\), and since this is repeated \(Q\) times, the overall complexity is \(O(Q \log N)\).

Implementation Notes

• Follows a common segment tree implementation using 1-indexed notation

• Uses sys.stdin.read for fast input reading

• Segment tree nodes are managed in the range [1, 2*size)

• Intervals need to be converted to 0-indexed before being passed (since the input is 1-indexed, we use l-1, r-1)

  Source Code

class LazySegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [0] * (2 * self.size)
        self.lazy = [0] * (2 * self.size)
        
        for i in range(self.n):
            self.tree[self.size + i] = data[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
    
    def _push(self, node, L, R):
        if self.lazy[node] != 0:
            self.tree[node] += self.lazy[node] * (R - L + 1)
            if L != R:
                self.lazy[2 * node] += self.lazy[node]
                self.lazy[2 * node + 1] += self.lazy[node]
            self.lazy[node] = 0
    
    def _update(self, node, L, R, l, r, val):
        self._push(node, L, R)
        if R < l or r < L:
            return
        if l <= L and R <= r:
            self.lazy[node] += val
            self._push(node, L, R)
            return
        mid = (L + R) // 2
        self._update(2 * node, L, mid, l, r, val)
        self._update(2 * node + 1, mid + 1, R, l, r, val)
        self._push(2 * node, L, mid)
        self._push(2 * node + 1, mid + 1, R)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def _query(self, node, L, R, l, r):
        if R < l or r < L:
            return 0
        self._push(node, L, R)
        if l <= L and R <= r:
            return self.tree[node]
        mid = (L + R) // 2
        left_sum = self._query(2 * node, L, mid, l, r)
        right_sum = self._query(2 * node + 1, mid + 1, R, l, r)
        return left_sum + right_sum
    
    def update(self, l, r, val):
        self._update(1, 0, self.size - 1, l, r, val)
    
    def query(self, l, r):
        return self._query(1, 0, self.size - 1, l, r)

import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1
    C = [int(data[idx + i]) for i in range(N)]
    idx += N
    
    seg_tree = LazySegmentTree(C)
    
    results = []
    for _ in range(Q):
        if data[idx] == '1':
            l = int(data[idx+1]) - 1
            r = int(data[idx+2]) - 1
            v = int(data[idx+3])
            idx += 4
            seg_tree.update(l, r, v)
        else:
            l = int(data[idx+1]) - 1
            r = int(data[idx+2]) - 1
            idx += 3
            res = seg_tree.query(l, r)
            results.append(str(res))
    
    print('\n'.join(results))

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.