概要

この問題は、配列に対する範囲更新（水やり）と範囲合計クエリ（確認）を効率的に処理するデータ構造を設計する問題です。

考察

素朴なアプローチでは、操作1ごとに \(O(N)\) 時間かけて配列を更新し、操作2でも \(O(N)\) 時間かけて合計を計算すると、全体で \(O(NQ)\) 時間かかり、\(N, Q\) が最大 \(10^5\) の場合 \(10^{10}\) 回の操作が必要となり、時間制限に間に合いません。

そこで、Fenwick Tree（Binary Indexed Tree）を用いて効率的に処理します。しかし、通常のFenwick Treeでは範囲更新と範囲合計クエリの両方を効率的に処理できません。この問題では、範囲更新を効率的に扱うために、数学的な式変形と2つのFenwick Treeを組み合わせるテクニックを使用します。

アルゴリズム

範囲更新と範囲合計クエリを効率的に処理するために、以下の数学的観察を利用します：

配列 \(A\) の区間 \([l, r]\) に値 \(v\) を加算する操作を考えます。このとき、区間 \([1, x]\) の合計 \(S(x)\) は以下のように表せます：

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

ここで \(\text{update}_i\) は位置 \(i\) で開始される更新の量を表します。この式を変形すると：

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

この式を実現するために、2つのFenwick Treeを使用します： 1. fenw_add: 通常の範囲加算用Fenwick Tree（\(\sum \text{update}_i\) を管理） 2. fenw: 変形された合計値を管理するFenwick Tree

操作1（1 l r v）では： - fenw_add に範囲 \([l, r]\) への加算を記録 - fenw には \((n-l+1) \cdot v\) を位置 \(l\) に加算し、\((n-r) \cdot v\) を位置 \(r+1\) に減算

操作2（2 l r）では： - \(S(r) - S(l-1)\) を計算 - \(S(x) = \text{fenw.query}(x) - (n - x) \cdot \text{fenw\_add.query}(x)\)

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • Fenwick Treeの各操作が \(O(\log N)\) 時間
  • 初期化に \(O(N \log N)\)、各クエリ処理に \(O(\log N)\)
• 空間計算量: \(O(N)\)
  • 2つのFenwick Treeを保持するため

実装のポイント

1. 2つのFenwick Treeを組み合わせて使用する

2. 範囲更新時に、数学的な式変形に基づいて適切な値を各位置に加算する

3. クエリ処理時には、2つのFenwick Treeから得られた値を組み合わせて正しい合計値を計算する

4. インデックス処理（1-indexed）に注意する

   ソースコード

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

---

この解説は deepseekv3 によって生成されました。