概要

この問題は、区間更新と区間和取得を効率的に行う必要がある典型的な遅延セグメント木（Lazy Segment Tree）の問題です。

考察

この問題では、花壇に水を追加する操作（区間更新）と、ある範囲の花壇の水の合計を求める操作（区間和取得）が複数回行われます。

素朴な方法として、操作ごとに配列を直接更新・合計を計算することもできますが、最悪ケースではそれぞれの操作で \(O(N)\) かかるため、全体で \(O(Q \cdot N)\) となり、制約 \(N, Q \leq 10^5\) よりTLEします。

そこで、区間に対する更新と取得を高速に行える「遅延セグメント木」を使用することで、各操作を \(O(\log N)\) で処理することが可能になります。

アルゴリズム

この問題を解くために使用したのは 遅延セグメント木（Lazy Segment Tree） です。

遅延セグメント木は、以下のような特徴を持ちます：

• 区間に対する値の更新（例：区間に \(v\) を加算）
• 区間に対する値の取得（例：区間和）
• これらを効率的に \(O(\log N)\) で行える

クラスの主な役割

• tree: 各区間の合計値を持つ通常のセグメント木
• lazy: 遅延評価用の配列。区間に一様に加算すべき値を保持

処理の流れ

1. 初期データからセグメント木を構築
2. 操作1（区間更新）に対しては update(l, r, v) を呼び出し、区間 \([l, r]\) に \(v\) を加算
3. 操作2（区間和取得）に対しては query(l, r) を呼び出して結果を出力

内部的には _push 関数で遅延情報を子ノードに伝播させ、常に最新の情報を保ちます。

計算量

• 時間計算量: \(O(Q \log N)\)
• 空間計算量: \(O(N)\)

各操作が \(O(\log N)\) であり、それが \(Q\) 回繰り返されるため、全体では \(O(Q \log N)\) となります。

実装のポイント

• 1-indexed で扱う一般的なセグメント木の実装に従っている
• 入力を高速に読み込むために sys.stdin.read を使用している
• セグメント木のノードは [1, 2*size) の範囲で管理されている
• 区間は0-indexedに変換してから渡す必要がある（入力が1-indexedなので l-1, r-1としている）

## ソースコード

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

---

この解説は qwen3-coder-480b によって生成されました。