Overview

Given \(N\) flower beds arranged in a row, this problem requires efficiently processing “range uniform addition” and “range sum query” operations. By using two Binary Indexed Trees (BITs), both operations can be performed in \(O(\log N)\).

Analysis

Problems with the Naive Approach

The simplest method is to manage the array directly.

• Operation 1 (range addition): Add \(v\) to each element from \(l\) to \(r\) → \(O(N)\)
• Operation 2 (range sum): Sum up all elements from \(l\) to \(r\) → \(O(N)\)

Since both \(N\) and \(Q\) can be up to \(10^5\), the worst case is \(O(NQ) = O(10^{10})\), which will not fit within the time limit.

Key Insight

This problem requires performing two operations efficiently: “range addition” and “range sum query”. This is a classic data structure problem that can be solved with the following approaches:

• Segment tree (with lazy propagation)
• Using two BITs (Binary Indexed Trees)

Here, we adopt the method using two BITs, which has a relatively simple implementation.

Algorithm

Principle of Range Addition and Range Sum Query with BIT

Consider the operation of adding value \(x\) to the interval \([l, r]\) from the perspective of prefix sums.

Introducing a difference array \(d\), where \(d[i]\) represents “the increment added at position \(i\)”, the total from position \(1\) to \(i\) (prefix sum) is:

\[\text{prefix\_sum}(i) = \sum_{j=1}^{i} \sum_{k=1}^{j} d[k]\]

Rearranging this:

\[\text{prefix\_sum}(i) = \sum_{k=1}^{i} d[k] \cdot (i - k + 1) = (i+1)\sum_{k=1}^{i} d[k] - \sum_{k=1}^{i} d[k] \cdot k\]

Two types of prefix sums appear in this formula:

• \(\text{bit1}\): manages the prefix sum of \(d[k]\)
• \(\text{bit2}\): manages the prefix sum of \(d[k] \cdot (k-1)\)

This gives us:

\[\text{prefix\_sum}(i) = \text{bit1\_sum}(i) \times i - \text{bit2\_sum}(i)\]

Adding to the interval \([l, r]\) only requires updating two positions each in \(\text{bit1}\) and \(\text{bit2}\).

Handling Initial Values

For the initial values \(C_i\), we separate them from the additions made by operations and precompute a prefix sum array prefix. When answering operation 2, we add together the range sum of initial values and the range sum of additions managed by the BIT.

Concrete Example

When \(N=5\), \(C = [3, 1, 4, 1, 5]\): - prefix = [0, 3, 4, 8, 9, 14] - Operation 1 2 4 2 (add 2 liters to flower beds 2–4) → range addition to BIT - Operation 2 1 5 (total of flower beds 1–5) → \(\text{prefix}[5] - \text{prefix}[0] + \text{bit.range\_sum}(1,5) = 14 + 6 = 20\)

Complexity

• Time complexity: \(O((N + Q) \log N)\) (\(O(N)\) for initialization, \(O(\log N)\) per query)
• Space complexity: \(O(N)\) (two BITs and the prefix sum array)

Implementation Notes

• Separating initial values and additions: Initial values are preprocessed with a prefix sum array, and the BIT only manages additions from operation 1. This eliminates the need for BIT initialization and simplifies the implementation.

• 1-indexed: BIT is naturally handled as 1-indexed. The flower bed numbers from the input can be used directly.

• Batch output: Using sys.stdout.write to output all at once reduces I/O overhead in Python.

  Source Code

import sys
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit1 = [0] * (n + 1)
        self.bit2 = [0] * (n + 1)
    
    def _add(self, bit, i, x):
        while i <= self.n:
            bit[i] += x
            i += i & (-i)
    
    def _sum(self, bit, i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s
    
    def range_add(self, l, r, x):
        self._add(self.bit1, l, x)
        self._add(self.bit1, r + 1, -x)
        self._add(self.bit2, l, x * (l - 1))
        self._add(self.bit2, r + 1, -x * r)
    
    def prefix_sum(self, i):
        return self._sum(self.bit1, i) * i - self._sum(self.bit2, i)
    
    def range_sum(self, l, r):
        return self.prefix_sum(r) - self.prefix_sum(l - 1)

def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    
    bit = BIT(N)
    
    # Initialize: add each C[i] as a point update (range of length 1)
    # Use prefix sum array for initial values
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + C[i]
    
    out = []
    for _ in range(Q):
        query = list(map(int, input().split()))
        if query[0] == 1:
            l, r, v = query[1], query[2], query[3]
            bit.range_add(l, r, v)
        else:
            l, r = query[1], query[2]
            ans = (prefix[r] - prefix[l - 1]) + bit.range_sum(l, r)
            out.append(ans)
    
    sys.stdout.write('\n'.join(map(str, out)) + '\n')

main()

---

This editorial was generated by claude4.6opus-thinking.