\(A\) の累積和をとった数列を \(S=(S_0,S_1,\dots,S_N)\) とおきます。すなわち、\(S_i =A_1 + \dots + A_i\) です。

\(A_x\) と \(A_{x+1}\) の値を入れ替えたとき、\(S\) の各要素の値がどのように変化するか考えます。まず、\(S_i\ (i < x)\) の値は明らかに変化しません。加えて、\(A_x + A_{x+1}\) の値が変化しないことから、\(S_i\ (i \geq x+1)\) の値もまた変化しません。よって、値が変化するのは \(S_{x}\) のみであり、変化後の値は \(S_{x-1}\) に（値を入れ替えた後の）\(A_{x}\) を足すことで簡単に求まります。

したがって、これを用いて \(A\) とともに \(S\) も同時に管理すれば、\(2\) 種類目のクエリに対しては \(S_r - S_{l-1}\) を求めて出力するのみとなり、クエリ毎 \(O(1)\) で本問題を解くことができます。

実装例 (C++) :

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> a(n), s(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s[i + 1] = s[i] + a[i];
    }
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x;
            cin >> x;
            --x;
            swap(a[x], a[x + 1]);
            s[x + 1] = s[x] + a[x];
        } else {
            int l, r;
            cin >> l >> r;
            --l;
            cout << s[r] - s[l] << '\n';
        }
    }
}