概要

この問題は、配列に対する「区間加算（Range Update）」と「区間和の取得（Range Sum Query）」を効率的に行う問題です。

花壇の数 \(N\) と操作の数 \(Q\) がともに最大 \(10^5\) と大きいため、愚直に配列を更新・走査する方法では間に合いません。データ構造を工夫して高速に処理する必要があります。

考察

1. 愚直な方法の限界

操作 1（水やり）で \(l\) から \(r\) までの要素すべてに \(v\) を加算し、操作 2（確認）で \(l\) から \(r\) までの合計を計算するとします。 最悪の場合、1回の操作に \(O(N)\) の時間がかかります。操作は \(Q\) 回行われるため、全体の計算量は \(O(NQ)\) となります。 \(N, Q = 10^5\) のとき、\(NQ = 10^{10}\) となり、一般的な実行時間制限（2秒程度）を大幅に超えてしまいます（通常 \(10^8\) 回程度の計算が限界です）。

2. 効率的なアプローチ

「区間の更新」と「区間の和」を同時に高速化できるデータ構造が必要です。代表的なものに以下の2つがあります。 - 遅延評価セグメント木 (Lazy Segment Tree): 一般的な手法ですが、実装がやや複雑です。 - 2つの Binary Indexed Tree (BIT): 実装が軽量で、今回の「加算」と「和」の操作であれば BIT 2つで対応可能です。

正解コードでは、実装のシンプルさと実行速度の面から BIT を2つ使う手法 を採用しています。

アルゴリズム

BITによる区間更新と区間和

通常、BITは「点更新」と「累積和（区間和）」を \(O(\log N)\) で行うデータ構造ですが、数式を変形することで「区間更新」と「区間和」にも対応できます。

配列 \(C\) の階差数列を \(D\) とします（\(D_i = C_i - C_{i-1}\)）。このとき、ある要素 \(C_i\) は \(C_i = \sum_{j=1}^i D_j\) と表せます。 求めたい \(k\) までの累積和 \(S_k = \sum_{i=1}^k C_i\) は、以下のように変形できます。

\[ \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} \]

この式を見ると、以下の2つの値を管理できれば累積和が求まることがわかります。 1. \(\sum D_j\) （階差数列の和） \(\rightarrow\) BIT1 で管理 2. \(\sum (j \cdot D_j)\) （インデックスを掛けた階差数列の和） \(\rightarrow\) BIT2 で管理

操作1：区間 \([l, r]\) に \(v\) を加算

階差数列 \(D\) においては、インデックス \(l\) に \(+v\)、インデックス \(r+1\) に \(-v\) するだけで区間更新を表現できます。 - BIT1: \(l\) に \(v\) を加算、\(r+1\) に \(-v\) を加算 - BIT2: \(l\) に \(l \cdot v\) を加算、\(r+1\) に \((r+1) \cdot (-v)\) を加算

操作2：区間 \([l, r]\) の和を取得

\((\text{累積和 } S_r) - (\text{累積和 } S_{l-1})\) を計算します。各累積和は上記の変形した式を用いて、2つの BIT から取得します。

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • 初期値の構築に \(O(N)\) または \(O(N \log N)\)
  • 各クエリに対し \(O(\log N)\)
• 空間計算量: \(O(N)\)
  • サイズ \(N\) の BIT を 2 つ使用

実装のポイント

• 高速な入出力: Pythonでは input() を繰り返すと遅いため、sys.stdin.read().split() で一括読み込みを行うのが一般的です。

• 1-indexed: BITは構造上、インデックスを 1 から始める必要があるため、配列のサイズやループの範囲に注意します。

• 初期値の処理: 最初に与えられる \(C_i\) も、「区間 \([i, i]\) に \(C_i\) を加算する」という操作 1 とみなして処理するか、階差をとって \(O(N)\) で BIT を構築します。

  ソースコード

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()

---

この解説は gemini-3-flash-thinking によって生成されました。