#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>


void solve() {
    int n, m;
    cin >> n >> m;

    vector<array<int, 5>> a;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        a.push_back({i, 0, 1, x, 0});
    }

    vector<bool> isq(m + 1);
    vector<ll> ans(m + 1);
    for (int i = 1; i <= m; i++) {
        int o, x, y;
        cin >> o >> x >> y;
        if (o == 1) {
            a.push_back({x, i, o, y, 0});
        } else {
            isq[i] = 1;
            a.push_back({y, i, o, 1, i});
            if (x > 1) a.push_back({x - 1, i, o, -1, i});
        }
    }

    function<void(int, int)> cdq = [&] (int l, int r) {
        if (l == r) return;
        int m = l + r >> 1;
        cdq(l, m); cdq(m + 1, r);
        sort(a.begin() + l, a.begin() + m + 1);
        sort(a.begin() + m + 1, a.begin() + r + 1);
        ll sum = 0;
        for (int j = m + 1, i = l; j <= r; j++) {
            while (i <= m) {
                if (a[i][2] == 2) {
                    i++;
                } else {
                    if (a[i][0] <= a[j][0]) {
                        sum += a[i][3];
                        i++;
                    } else {
                        break;
                    }
                }
            }
            if (a[j][2] == 2) {
                ans[a[j][4]] += a[j][3] * sum;
            }
        }
    };
    cdq(0, (int)a.size() - 1);
    for (int i = 1; i <= m; i++) if (isq[i]) cout << ans[i] << '\n';
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}
/*
g++ -std=c++14 1.cpp -o 1 && 1 < in.txt > out.txt
g++ -std=c++17 1.cpp -o 1 && ./1 < in.txt > out.txt

*/