1 x のクエリは次のように分解できます。

1. \(v \leftarrow A_x, w \leftarrow A_{x+1}\) とする。
2. \(A_x \leftarrow w\) とする
3. \(A_{x+1} \leftarrow v\) とする

一点変更が 2 回行われています。

2 x のクエリは区間和クエリです。

よって、一点変更と区間和取得のクエリが高速に処理できるデータ構造があればよいです。BIT（フェニック木） やセグメント木を使うと、どちらのクエリも \(O(\log N)\) 時間で実現できます。

時間計算量は \(O((N+Q)\log N)\)、空間計算量は \(O(N)\) です。

BIT とセグメント木のどちらも ACL (AtCoder Library) にあります。

BIT を使うコード例

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/fenwicktree>

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	for (int i=0; i<n; i++) {
		cin >> a[i];
	}

	atcoder::fenwick_tree<int> fw(n);
	for (int i=0; i<n; i++) {
		fw.add(i, + a[i]);
	}

	while(q--) {
		int t; cin >> t;
		if (t == 1) {
			int x; cin >> x;
			x--;
			fw.add(x, - a[x]);
			fw.add(x + 1, - a[x + 1]);
			swap(a[x], a[x + 1]);
			fw.add(x, + a[x]);
			fw.add(x + 1, + a[x + 1]);
		} else {
			int l, r; cin >> l >> r;
			l--;
			cout << fw.sum(l, r) << '\n';
		}
	}
}

セグメント木を使うコード例

前計算が \(O(N)\) 時間で行えるため、時間計算量は \(O(Q \log N + N)\) です。

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/segtree>

int op(int a, int b) { return a + b; }
int e() { return 0; }

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	for (int i=0; i<n; i++) {
		cin >> a[i];
	}

	atcoder::segtree<int,op,e> seg(a);

	while(q--) {
		int t; cin >> t;
		if (t == 1) {
			int x; cin >> x;
			x--;
			swap(a[x], a[x + 1]);
			seg.set(x, a[x]);
			seg.set(x + 1, a[x + 1]);
		} else {
			int l, r; cin >> l >> r;
			l--;
			cout << seg.prod(l, r) << '\n';
		}
	}
}