// ══════════════════════════════════════════════════════════════
// 树状数组（BIT）—— 经典实现
// 支持：单点更新 O(log N)，前缀和查询 O(log N)
// 数组必须使用 1-indexed（关键！）
// ══════════════════════════════════════════════════════════════
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;

int n;
long long tree[MAXN];  // BIT 数组，1-indexed

// ── lowbit：返回最低位 1 的值 ──
inline int lowbit(int x) {
    return x & (-x);
}

// ── 更新：给位置 i 加 val ──
// 向上遍历：i += lowbit(i)
// 覆盖位置 i 的每个祖先节点都被更新
void update(int i, long long val) {
    for (; i <= n; i += lowbit(i))
        tree[i] += val;
    // 时间：O(log N) — 最多 log2(N) 次迭代
}

// ── 查询：返回前缀和 A[1..i] ──
// 向下遍历：i -= lowbit(i)
// 将 [1..i] 分解为 O(log N) 个不重叠的区间
long long query(int i) {
    long long sum = 0;
    for (; i > 0; i -= lowbit(i))
        sum += tree[i];
    return sum;
    // 时间：O(log N) — 最多 log2(N) 次迭代
}

// ── 构建：从已有数组 A[1..n] 初始化 BIT ──
// 方法一：N 次单独更新 — O(N log N)
void build_slow(long long A[]) {
    fill(tree + 1, tree + n + 1, 0LL);
    for (int i = 1; i <= n; i++)
        update(i, A[i]);
}

// 方法二：O(N) 构建（利用「直接父节点」关系）
void build_fast(long long A[]) {
    for (int i = 1; i <= n; i++) {
        tree[i] += A[i];
        int parent = i + lowbit(i);  // BIT 中的直接父节点
        if (parent <= n)
            tree[parent] += tree[i];
    }
}

// 方法三：O(N) 构建（利用前缀和）
// 原理：tree[i] = sum(A[i-lowbit(i)+1 .. i])
//      = prefix[i] - prefix[i - lowbit(i)]
void build_prefix(long long A[], long long prefix[]) {
    // 先求前缀和
    for (int i = 1; i <= n; i++) prefix[i] = prefix[i-1] + A[i];
    // 利用前缀和直接计算每个节点
    for (int i = 1; i <= n; i++)
        tree[i] = prefix[i] - prefix[i - lowbit(i)];
}

// ── 完整示例 ──
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int q;
    cin >> n >> q;

    long long A[MAXN] = {};
    for (int i = 1; i <= n; i++) cin >> A[i];
    build_fast(A);  // O(N) 初始化

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            // 单点更新：A[i] += val
            int i; long long val;
            cin >> i >> val;
            update(i, val);
        } else {
            // 前缀查询：A[1..r] 的和
            int r;
            cin >> r;
            cout << query(r) << "\n";
        }
    }
    return 0;
}

A[l..r] = A[1..r] - A[1..l-1]

// 区间求和：A[l..r] 的和
// 时间：O(log N) — 两次前缀查询
long long range_query(int l, int r) {
    return query(r) - query(l - 1);
    // query(r)   = A[1] + A[2] + ... + A[r]
    // query(l-1) = A[1] + A[2] + ... + A[l-1]
    // 差值        = A[l] + A[l+1] + ... + A[r]
}

// 示例：
// A = [3, 1, 4, 1, 5, 9, 2, 6]  (1-indexed)
// range_query(3, 6) = query(6) - query(2)
//                  = (3+1+4+1+5+9) - (3+1)
//                  = 23 - 4 = 19
// 验证：A[3]+A[4]+A[5]+A[6] = 4+1+5+9 = 19 ✓

// ══════════════════════════════════════════════════════════════
// 差分 BIT：区间更新 + 单点查询
// ══════════════════════════════════════════════════════════════
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;
int n;
long long diff_bit[MAXN];  // 差分数组 D[] 上的 BIT

inline int lowbit(int x) { return x & (-x); }

// 更新差分 BIT 的位置 i：D[i] += val
void diff_update(int i, long long val) {
    for (; i <= n; i += lowbit(i))
        diff_bit[i] += val;
}

// 查询 A[i] = D[1..i] 的和 = 差分 BIT 的前缀查询
long long diff_query(int i) {
    long long s = 0;
    for (; i > 0; i -= lowbit(i))
        s += diff_bit[i];
    return s;
}

// 区间更新：给 A[l..r] 全部加 val
// 等价于：D[l] += val，D[r+1] -= val
void range_update(int l, int r, long long val) {
    diff_update(l, val);       // D[l] += val
    diff_update(r + 1, -val);  // D[r+1] -= val
}

// 单点查询：返回 A[i] 的当前值
// A[i] = D[1] + D[2] + ... + D[i] = prefix_sum(D, i)
long long point_query(int i) {
    return diff_query(i);
}

// ══════════════════════════════════════════════════════════════
// 双 BIT：区间更新 + 区间查询
// 公式：sum(1..r) = B1[r] * r - B2[r]
// 其中 B1 是 D[] 上的 BIT，B2 是 (i-1)*D[i] 上的 BIT
// ══════════════════════════════════════════════════════════════
long long B1[MAXN], B2[MAXN];

inline int lowbit(int x) { return x & (-x); }

void add(long long* b, int i, long long v) {
    for (; i <= n; i += lowbit(i)) b[i] += v;
}
long long sum(long long* b, int i) {
    long long s = 0;
    for (; i > 0; i -= lowbit(i)) s += b[i];
    return s;
}

// 区间更新：给 A[l..r] 加 val
void range_add(int l, int r, long long val) {
    add(B1, l, val);
    add(B1, r + 1, -val);
    add(B2, l, val * (l - 1));     // 补偿前缀公式
    add(B2, r + 1, -val * r);
}

// 前缀和 A[1..r]
long long prefix_sum(int r) {
    return sum(B1, r) * r - sum(B2, r);
}

// 区间和 A[l..r]
long long range_sum(int l, int r) {
    return prefix_sum(r) - prefix_sum(l - 1);
}

// ══════════════════════════════════════════════════════════════
// 用树状数组统计逆序对 — O(N log N)
//
// 核心思路：
//   从左到右处理 A[i]。
//   对每个 A[i]，以 A[i] 为右端点的逆序对数
//   = 已处理过的值中大于 A[i] 的数量
//   = (目前处理的元素数) - (已处理的 <= A[i] 的元素数)
//   = i-1 - prefix_query(A[i])
//   对所有 i 求和即为总逆序对数。
//
// BIT 的作用：追踪已见过的值的频率。
//   见到值 v 后：update(v, +1)
//   查询 <= x 的值的数量：query(x)
// ══════════════════════════════════════════════════════════════
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 300005;

int n;
int bit[MAXN];  // 频率计数 BIT

inline int lowbit(int x) { return x & (-x); }

// 在位置 v 加 1（见到了值 v）
void update(int v) {
    for (; v <= n; v += lowbit(v))
        bit[v]++;
}

// 统计已见过的 [1..v] 中的值的数量
int query(int v) {
    int cnt = 0;
    for (; v > 0; v -= lowbit(v))
        cnt += bit[v];
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;

    ll inversions = 0;

    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;

        // 统计以 a 为右端点的逆序对：
        // 已见过的值中大于 a 的数量
        // = (目前已见 i-1 个元素) - (已见的 <= a 的数量)
        int less_or_equal = query(a);          // [1..a] 中已见的数量
        int greater = (i - 1) - less_or_equal; // [a+1..n] 中已见的数量
        inversions += greater;

        // 标记我们已见过值 a
        update(a);
    }

    cout << inversions << "\n";
    return 0;
}

/*
对 A = [3, 1, 4, 2, 5] 的追踪：

i=1, a=3：已见=[]，query(3)=0，greater=0-0=0。逆序对=0。update(3)。
i=2, a=1：已见=[3]，query(1)=0，greater=1-0=1。逆序对=1。update(1)。
           （3 > 1：1 个逆序对：(3,1) ✓）
i=3, a=4：已见=[3,1]，query(4)=2，greater=2-2=0。逆序对=1。update(4)。
           （没有已见的元素 > 4）
i=4, a=2：已见=[3,1,4]，query(2)=1，greater=3-1=2。逆序对=3。update(2)。
           （3>2 且 4>2：2 个逆序对：(3,2),(4,2) ✓）
i=5, a=5：已见=[3,1,4,2]，query(5)=4，greater=4-4=0。逆序对=3。update(5)。

最终：3 ✓
*/

// 任意值的坐标压缩
vector<int> A(n);
for (int i = 0; i < n; i++) cin >> A[i];

// 步骤一：排序去重
vector<int> sorted_A = A;
sort(sorted_A.begin(), sorted_A.end());
sorted_A.erase(unique(sorted_A.begin(), sorted_A.end()), sorted_A.end());

// 步骤二：将每个值替换为它的排名（1-indexed）
for (int i = 0; i < n; i++) {
    A[i] = lower_bound(sorted_A.begin(), sorted_A.end(), A[i]) - sorted_A.begin() + 1;
    // A[i] 现在在 [1..M]，M = sorted_A.size()
}
// 现在用 n = sorted_A.size() 使用 BIT

// 在值域 [1..MAXV] 上的 BIT 中，找第 k 小的值
int kth_binary_search(int k) {
    int lo = 1, hi = MAXV;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (query(mid) >= k)
            hi = mid;
        else
            lo = mid + 1;
    }
    return lo;
}

// 全局第 k 小（倍增法）— O(log N)
// 前提：BIT 维护值域频率，bit[v] = v 的出现次数
int kth(int k) {
    int sum = 0, x = 0;
    // 从最高位开始，逐位确定答案
    for (int i = (int)log2(MAXV); i >= 0; --i) {
        int nx = x + (1 << i);
        if (nx <= MAXV && sum + bit[nx] < k) {
            x = nx;          // 这一段全选，继续向右扩展
            sum += bit[nx];
        }
        // 否则答案在 [x+1, x + 2^(i-1)] 范围内，不扩展
    }
    return x + 1;  // x 是最后一个 sum < k 的位置，答案是 x+1
}

// 完整示例：动态维护序列，支持插入和第 k 小查询
// 插入值 v：update(v, 1)
// 删除值 v：update(v, -1)
// 查询第 k 小：kth(k)

// ❌ 错误 — 多组测试数据时
int T; cin >> T;
while (T--) {
    // 忘记清空 tree[]！
    // 上一组测试数据的旧数据污染结果
    solve();
}

// ✅ 正确 — 每组测试数据前重置
int T; cin >> T;
while (T--) {
    fill(tree + 1, tree + n + 1, 0LL);  // 清空 BIT
    solve();
}

🟢 简单一：区间求和

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, q;
long long tree[MAXN];
int lowbit(int x) { return x & (-x); }
void update(int i, long long val) { for (; i <= n; i += lowbit(i)) tree[i] += val; }
long long query(int i) { long long s=0; for (; i > 0; i -= lowbit(i)) s += tree[i]; return s; }
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> q;
    while (q--) {
        int t; cin >> t;
        if (t == 1) { int i; long long x; cin >> i >> x; update(i, x); }
        else { int l, r; cin >> l >> r; cout << query(r) - query(l-1) << "\n"; }
    }
}

🟡 中等一：区间加法，单点查询（差分 BIT） 核心思路：在 BIT 中维护差分数组。range_add(l,r,x) = update(l,x) + update(r+1,-x)。单点查询 = query(i)。

void range_add(int l, int r, long long x) { update(l, x); update(r+1, -x); }
long long point_query(int i) { return query(i); }

🟡 中等二：逆序对计数

// 先坐标压缩，然后对每个元素 x：
// 逆序对 += (已插入的元素数) - query(压缩后的 x)
// 然后插入 x：update(压缩后的 x, 1)

🔴 困难：区间加法，区间求和（双 BIT）

// prefix_sum(r) = (r+1)*sum(D[1..r]) - sum(i*D[i], i=1..r)
// = (r+1)*B1.query(r) - B2.query(r)
// 其中 B1 存 D[i]，B2 存 i*D[i]
struct DoubleBIT {
    long long B1[MAXN], B2[MAXN];
    int n;
    DoubleBIT(int n) : n(n) { memset(B1,0,sizeof(B1)); memset(B2,0,sizeof(B2)); }
    void add(int i, long long v) {
        for (int x=i; x<=n; x+=x&-x) { B1[x]+=v; B2[x]+=v*i; }
    }
    void range_add(int l, int r, long long v) { add(l,v); add(r+1,-v); }
    long long prefix(int i) {
        long long s=0; for(int x=i;x>0;x-=x&-x) s+=(i+1)*B1[x]-B2[x]; return s;
    }
    long long range_query(int l, int r) { return prefix(r)-prefix(l-1); }
};