Overview

This problem requires efficiently performing “Range Update” (range addition) and “Range Sum Query” on an array.

Since both the number of flower beds \(N\) and the number of operations \(Q\) can be as large as \(10^5\), a naive approach of directly updating and scanning the array will not be fast enough. We need to use a clever data structure to process operations efficiently.

Analysis

1. Limitations of the Naive Approach

Suppose operation 1 (watering) adds \(v\) to all elements from \(l\) to \(r\), and operation 2 (checking) computes the sum from \(l\) to \(r\). In the worst case, a single operation takes \(O(N)\) time. Since there are \(Q\) operations, the total time complexity is \(O(NQ)\). When \(N, Q = 10^5\), we get \(NQ = 10^{10}\), which far exceeds the typical time limit (around 2 seconds), as roughly \(10^8\) operations is the usual limit.

2. Efficient Approach

We need a data structure that can simultaneously speed up both “range updates” and “range sum queries.” Two well-known options are: - Lazy Segment Tree: A general technique, but the implementation is somewhat complex. - Two Binary Indexed Trees (BITs): A lightweight implementation that can handle “addition” and “sum” operations using just two BITs.

The correct solution adopts the two-BIT approach for its simplicity of implementation and execution speed.

Algorithm

Range Update and Range Sum with BITs

Normally, a BIT is a data structure that performs “point updates” and “prefix sum (range sum) queries” in \(O(\log N)\). However, by transforming the formulas, it can also handle “range updates” and “range sum queries.”

Let \(D\) be the difference array of array \(C\) (i.e., \(D_i = C_i - C_{i-1}\)). Then, any element \(C_i\) can be expressed as \(C_i = \sum_{j=1}^i D_j\). The desired prefix sum up to \(k\), \(S_k = \sum_{i=1}^k C_i\), can be transformed as follows:

\[ \begin{aligned} S_k = \sum_{i=1}^k C_i &= \sum_{i=1}^k \sum_{j=1}^i D_j \\ &= \sum_{j=1}^k (k - j + 1) D_j \\ &= (k + 1) \sum_{j=1}^k D_j - \sum_{j=1}^k (j \cdot D_j) \end{aligned} \]

From this formula, we can see that the prefix sum can be computed if we maintain the following two values: 1. \(\sum D_j\) (sum of the difference array) \(\rightarrow\) managed by BIT1 2. \(\sum (j \cdot D_j)\) (sum of the difference array weighted by index) \(\rightarrow\) managed by BIT2

Operation 1: Add \(v\) to the range \([l, r]\)

In terms of the difference array \(D\), a range update can be represented by adding \(+v\) at index \(l\) and \(-v\) at index \(r+1\). - BIT1: Add \(v\) at \(l\), add \(-v\) at \(r+1\) - BIT2: Add \(l \cdot v\) at \(l\), add \((r+1) \cdot (-v)\) at \(r+1\)

Operation 2: Get the sum of the range \([l, r]\)

Compute \((\text{prefix sum } S_r) - (\text{prefix sum } S_{l-1})\). Each prefix sum is obtained from the two BITs using the transformed formula above.

Complexity

• Time Complexity: \(O((N + Q) \log N)\)
  • Building from initial values takes \(O(N)\) or \(O(N \log N)\)
  • Each query takes \(O(\log N)\)
• Space Complexity: \(O(N)\)
  • Two BITs of size \(N\) are used

Implementation Notes

• Fast I/O: In Python, repeatedly calling input() is slow, so it is common practice to read all input at once using sys.stdin.read().split().

• 1-indexed: Due to the structure of BITs, indices must start from 1, so care must be taken with array sizes and loop ranges.

• Handling Initial Values: The initially given \(C_i\) values can either be treated as operation 1 applied to the range \([i, i]\) adding \(C_i\), or the differences can be computed to build the BIT in \(O(N)\).

  Source Code

import sys

def solve():
    # Fast I/O: read all input at once and split into a list of strings
    try:
        input_all = sys.stdin.read().split()
    except EOFError:
        return
    if not input_all:
        return
    
    # N: number of flowerbeds, Q: number of operations
    N = int(input_all[0])
    Q = int(input_all[1])
    
    # We use two Binary Indexed Trees (BITs) to handle range updates and range sums.
    # Let D[i] be the difference array such that C[i] = sum(D[1...i]).
    # Then the prefix sum of C up to k is:
    # sum(C[1...k]) = (k + 1) * sum(D[1...k]) - sum(j * D[j] for j in 1...k)
    # bit1 stores D[j], and bit2 stores j * D[j].
    
    # size = N + 1 to handle range updates at r + 1 where r can be N
    size = N + 1
    bit1 = [0] * (size + 1)
    bit2 = [0] * (size + 1)
    
    # Process initial values of C_i (flowerbeds water amounts)
    # Initial values are at input_all[2] through input_all[N+1]
    prev_C = 0
    for i in range(1, N + 1):
        curr_C = int(input_all[i + 1])
        diff = curr_C - prev_C
        bit1[i] = diff
        bit2[i] = i * diff
        prev_C = curr_C
        
    # O(N) construction of BITs from the initial difference values
    for i in range(1, size + 1):
        j = i + (i & -i)
        if j <= size:
            bit1[j] += bit1[i]
            bit2[j] += bit2[i]
    
    ptr = N + 2
    results = []
    
    # Process Q operations
    for _ in range(Q):
        q_type = input_all[ptr]
        if q_type == '1':
            # Operation 1: Range Update [l, r] with value v
            l = int(input_all[ptr + 1])
            r = int(input_all[ptr + 2])
            v = int(input_all[ptr + 3])
            
            # Update bit1: add v at l, subtract v at r+1
            idx = l
            while idx <= size:
                bit1[idx] += v
                idx += idx & -idx
            idx = r + 1
            while idx <= size:
                bit1[idx] -= v
                idx += idx & -idx
            
            # Update bit2: add l*v at l, subtract (r+1)*v at r+1
            idx = l
            val_l = l * v
            while idx <= size:
                bit2[idx] += val_l
                idx += idx & -idx
            idx = r + 1
            val_r = (r + 1) * v
            while idx <= size:
                bit2[idx] -= val_r
                idx += idx & -idx
            ptr += 4
        else:
            # Operation 2: Range Sum Query [l, r]
            l = int(input_all[ptr + 1])
            r = int(input_all[ptr + 2])
            
            # Prefix sum up to r
            s1_r, s2_r = 0, 0
            i = r
            while i > 0:
                s1_r += bit1[i]
                s2_r += bit2[i]
                i -= i & -i
            ps_r = (r + 1) * s1_r - s2_r
            
            # Prefix sum up to l-1
            s1_l, s2_l = 0, 0
            i = l - 1
            while i > 0:
                s1_l += bit1[i]
                s2_l += bit2[i]
                i -= i & -i
            ps_l = l * s1_l - s2_l
            
            # The range sum [l, r] is prefix_sum(r) - prefix_sum(l-1)
            results.append(str(ps_r - ps_l))
            ptr += 3
            
    # Output all query results separated by newlines
    if results:
        sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.