// ══════════════════════════════════════════════════════════════
// Fenwick Tree (BIT) — Classic Implementation
// Supports: point update O(log N), prefix sum query O(log N)
// Array MUST use 1-indexed (critical!)
// ══════════════════════════════════════════════════════════════
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;

int n;
long long tree[MAXN];  // BIT array, 1-indexed

// ── lowbit: returns value of lowest set bit ──
inline int lowbit(int x) {
    return x & (-x);
}

// ── Update: add val to position i ──
// Traverse upward: i += lowbit(i)
// Every ancestor node covering position i is updated
void update(int i, long long val) {
    for (; i <= n; i += lowbit(i))
        tree[i] += val;
    // Time: O(log N) — at most log2(N) iterations
}

// ── Query: return prefix sum A[1..i] ──
// Traverse downward: i -= lowbit(i)
// Decompose [1..i] into O(log N) non-overlapping intervals
long long query(int i) {
    long long sum = 0;
    for (; i > 0; i -= lowbit(i))
        sum += tree[i];
    return sum;
    // Time: O(log N) — at most log2(N) iterations
}

// ── Build: initialize BIT from existing array A[1..n] ──
// Method 1: N separate updates — 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]);
}

// Method 2: O(N) build (using "direct parent" relationship)
void build_fast(long long A[]) {
    for (int i = 1; i <= n; i++) {
        tree[i] += A[i];
        int parent = i + lowbit(i);  // Direct parent in BIT
        if (parent <= n)
            tree[parent] += tree[i];
    }
}

// Method 3: O(N) build (using prefix sums)
// Principle: tree[i] = sum(A[i-lowbit(i)+1 .. i])
//          = prefix[i] - prefix[i - lowbit(i)]
void build_prefix(long long A[], long long prefix[]) {
    // Compute prefix sums first
    for (int i = 1; i <= n; i++) prefix[i] = prefix[i-1] + A[i];
    // Directly compute each node using prefix sums
    for (int i = 1; i <= n; i++)
        tree[i] = prefix[i] - prefix[i - lowbit(i)];
}

// ── Complete Example ──
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) initialization

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            // Point update: A[i] += val
            int i; long long val;
            cin >> i >> val;
            update(i, val);
        } else {
            // Prefix query: sum of A[1..r]
            int r;
            cin >> r;
            cout << query(r) << "\n";
        }
    }
    return 0;
}

// Range sum: sum of A[l..r]
// Time: O(log N) — two prefix queries
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]
    // difference = A[l] + A[l+1] + ... + A[r]
}

// Example:
// 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
// Verify: A[3]+A[4]+A[5]+A[6] = 4+1+5+9 = 19 ✓

// ══════════════════════════════════════════════════════════════
// Difference BIT: Range Update + Point Query
// ══════════════════════════════════════════════════════════════
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;
int n;
long long diff_bit[MAXN];  // BIT on difference array D[]

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

// Update difference BIT at position i: D[i] += val
void diff_update(int i, long long val) {
    for (; i <= n; i += lowbit(i))
        diff_bit[i] += val;
}

// Query A[i] = sum of D[1..i] = prefix query on difference BIT
long long diff_query(int i) {
    long long s = 0;
    for (; i > 0; i -= lowbit(i))
        s += diff_bit[i];
    return s;
}

// Range update: add val to all elements in A[l..r]
// Equivalent to: 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
}

// Point query: return current value of A[i]
// A[i] = D[1] + D[2] + ... + D[i] = prefix_sum(D, i)
long long point_query(int i) {
    return diff_query(i);
}

// ══════════════════════════════════════════════════════════════
// Double BIT: Range Update + Range Query
// Formula: sum(1..r) = B1[r] * r - B2[r]
// Where B1 is BIT on D[], B2 is BIT on (i-1)*D[i]
// ══════════════════════════════════════════════════════════════
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;
}

// Range update: add val to A[l..r]
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));     // Compensate for prefix formula
    add(B2, r + 1, -val * r);
}

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

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

// ══════════════════════════════════════════════════════════════
// Count Inversions with Fenwick Tree — O(N log N)
//
// Core Idea:
//   Process A[i] from left to right.
//   For each A[i], the number of inversions with A[i] as right endpoint
//   = number of already-processed values greater than A[i]
//   = (number of elements processed so far) - (number of processed elements <= A[i])
//   = i-1 - prefix_query(A[i])
//   Sum over all i gives total inversions.
//
// BIT's role: track frequency of seen values.
//   After seeing value v: update(v, +1)
//   Query count of values <= x: query(x)
// ══════════════════════════════════════════════════════════════
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 300005;

int n;
int bit[MAXN];  // Frequency count BIT

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

// Add 1 at position v (saw value v)
void update(int v) {
    for (; v <= n; v += lowbit(v))
        bit[v]++;
}

// Count values in [1..v] seen so far
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;

        // Count inversions with a as right endpoint:
        // Number of already-seen values greater than a
        // = (i-1 elements seen so far) - (count of seen values <= a)
        int less_or_equal = query(a);          // Count of [1..a] seen so far
        int greater = (i - 1) - less_or_equal; // Count of [a+1..n] seen so far
        inversions += greater;

        // Mark that we've seen value a
        update(a);
    }

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

/*
Trace for A = [3, 1, 4, 2, 5]:

i=1, a=3: seen=[], query(3)=0, greater=0-0=0. inversions=0. update(3).
i=2, a=1: seen=[3], query(1)=0, greater=1-0=1. inversions=1. update(1).
           (3 > 1: 1 inversion: (3,1) ✓)
i=3, a=4: seen=[3,1], query(4)=2, greater=2-2=0. inversions=1. update(4).
           (no seen elements > 4)
i=4, a=2: seen=[3,1,4], query(2)=1, greater=3-1=2. inversions=3. update(2).
           (3>2 and 4>2: 2 inversions: (3,2),(4,2) ✓)
i=5, a=5: seen=[3,1,4,2], query(5)=4, greater=4-4=0. inversions=3. update(5).

Final: 3 ✓
*/

// Coordinate compression for arbitrary values
vector<int> A(n);
for (int i = 0; i < n; i++) cin >> A[i];

// Step 1: Sort and deduplicate
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());

// Step 2: Replace each value with its rank (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] is now in [1..M], M = sorted_A.size()
}
// Now use BIT with n = sorted_A.size()

// ❌ Wrong — multiple test cases
int T; cin >> T;
while (T--) {
    // Forgot to clear tree[]!
    // Old data from previous test case contaminates results
    solve();
}

// ✅ Correct — reset before each test case
int T; cin >> T;
while (T--) {
    fill(tree + 1, tree + n + 1, 0LL);  // Clear BIT
    solve();
}

🟢 Easy 1: Range Sum

#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"; }
    }
}

🟡 Medium 1: Range Add, Point Query (Difference BIT) Core idea: maintain difference array in BIT. range_add(l,r,x) = update(l,x) + update(r+1,-x). Point query = 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); }

🟡 Medium 2: Inversion Count

// Coordinate compress first, then for each element x:
// inversions += (number of inserted elements) - query(compressed x)
// Then insert x: update(compressed x, 1)

🔴 Hard: Range Add, Range Sum (Double 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)
// Where B1 stores D[i], B2 stores 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); }
};

// Find K-th smallest value in BIT over value domain [1..MAXV]
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;
}

// Global K-th smallest (doubling method) — O(log N)
// Prerequisite: BIT maintains value domain frequency, bit[v] = count of v
int kth(int k) {
    int sum = 0, x = 0;
    // Determine answer bit by bit from highest to lowest
    for (int i = (int)log2(MAXV); i >= 0; --i) {
        int nx = x + (1 << i);
        if (nx <= MAXV && sum + bit[nx] < k) {
            x = nx;          // Take this entire segment, continue expanding right
            sum += bit[nx];
        }
        // Otherwise answer is in [x+1, x + 2^(i-1)], don't expand
    }
    return x + 1;  // x is the last position where sum < k, answer is x+1
}

// Complete example: dynamically maintain sequence, support insert and K-th smallest query
// Insert value v: update(v, 1)
// Delete value v: update(v, -1)
// Query K-th smallest: kth(k)