Overview

This problem requires designing a data structure that efficiently handles range updates (watering) and range sum queries (checking) on an array.

Analysis

In a naive approach, each operation 1 takes \(O(N)\) time to update the array, and each operation 2 takes \(O(N)\) time to compute the sum, resulting in \(O(NQ)\) total time. When \(N, Q\) are up to \(10^5\), this requires \(10^{10}\) operations, which will not fit within the time limit.

Therefore, we use a Fenwick Tree (Binary Indexed Tree) to process operations efficiently. However, a standard Fenwick Tree cannot efficiently handle both range updates and range sum queries. In this problem, we use a technique that combines mathematical formula transformation with two Fenwick Trees to efficiently handle range updates.

Algorithm

To efficiently process range updates and range sum queries, we use the following mathematical observation:

Consider the operation of adding value \(v\) to the interval \([l, r]\) of array \(A\). The prefix sum \(S(x)\) for interval \([1, x]\) can be expressed as:

\(S(x) = \sum_{i=1}^{x} A_i + \sum_{i=1}^{x} (x - i + 1) \cdot \text{update}_i\)

where \(\text{update}_i\) represents the amount of the update starting at position \(i\). Transforming this expression:

\(S(x) = \text{initial\_sum}(x) + (x+1) \cdot \sum_{i=1}^{x} \text{update}_i - \sum_{i=1}^{x} i \cdot \text{update}_i\)

To realize this formula, we use two Fenwick Trees: 1. fenw_add: A Fenwick Tree for standard range addition (managing \(\sum \text{update}_i\)) 2. fenw: A Fenwick Tree managing the transformed sum values

For operation 1 (1 l r v): - Record the addition to range \([l, r]\) in fenw_add - In fenw, add \((n-l+1) \cdot v\) at position \(l\) and subtract \((n-r) \cdot v\) at position \(r+1\)

For operation 2 (2 l r): - Compute \(S(r) - S(l-1)\) - \(S(x) = \text{fenw.query}(x) - (n - x) \cdot \text{fenw\_add.query}(x)\)

Complexity

• Time complexity: \(O((N + Q) \log N)\)
  • Each Fenwick Tree operation takes \(O(\log N)\) time
  • Initialization takes \(O(N \log N)\), and each query takes \(O(\log N)\)
• Space complexity: \(O(N)\)
  • For maintaining two Fenwick Trees

Implementation Notes

1. Use two Fenwick Trees in combination

2. During range updates, add appropriate values at each position based on the mathematical formula transformation

3. During query processing, combine the values obtained from both Fenwick Trees to compute the correct sum

4. Be careful with index handling (1-indexed)

   Source Code

import sys

class Fenw:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def update(self, index, delta):
        while index <= self.n:
            self.tree[index] += delta
            index += index & -index
    
    def query(self, index):
        s = 0
        while index:
            s += self.tree[index]
            index -= index & -index
        return s

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    n = int(next(it)); q = int(next(it))
    arr = [0] * (n + 1)
    for i in range(1, n + 1):
        arr[i] = int(next(it))
    
    fenw = Fenw(n)
    fenw_add = Fenw(n)
    
    for i in range(1, n + 1):
        fenw.update(i, arr[i])
    
    output_lines = []
    for _ in range(q):
        t = next(it)
        if t == '1':
            l = int(next(it)); r = int(next(it)); v = int(next(it))
            fenw_add.update(l, v)
            if r < n:
                fenw_add.update(r + 1, -v)
            fenw.update(l, v * (n - l + 1))
            if r < n:
                fenw.update(r + 1, -v * (n - r))
        else:
            l = int(next(it)); r = int(next(it))
            total_r = fenw.query(r) - fenw_add.query(r) * (n - r)
            total_l_minus = fenw.query(l - 1) - fenw_add.query(l - 1) * (n - l + 1)
            res = total_r - total_l_minus
            output_lines.append(str(res))
    
    print("\n".join(output_lines))

if __name__ == "__main__":
    main()

---

This editorial was generated by deepseekv3.