树状数组的逆序对统计与动态频次计数

核心逻辑与数学原理

树状数组（BIT）不仅可以维护显式的区间和，还能够作为动态频次计数器（Dynamic Frequency Counter）来维护权值空间。其核心逻辑是将原数组的值域映射为树状数组的下标，通过动态维护频次的前缀和，在 $O(\log N)$ 内完成各种高维序关系的统计。

1. 逆序对（Inversion Pair）的代数转化

对于一个序列 $A$，若满足 $i < j$ 且 $A[i] > A[j]$，则称 $(A[i], A[j])$ 为一个逆序对。当我们在权值空间内从左到右遍历序列 $A$ 时，设当前处理到 $A[j]$：

• 此时已经插入权值树状数组的元素，均满足输入序列的下标约束 $i < j$。
• 要在这些已插入的元素中寻找满足 $A[i] > A[j]$ 的数量，等价于求当前全集内大于 $A[j]$ 的频次之和。
• 利用补集思想，总已插入数减去小于等于 $A[j]$ 的数，即为当前元素催生的逆序对数：

$$\text{Count}(A[i] > A[j]) = \text{Query}(\text{MAX\_VAL}) - \text{Query}(A[j])$$

2. 离散化（Discretization）的几何映射

若序列元素 $A[i] \in [-10^9, 10^9]$，权值空间过大，无法直接作为树状数组下标。由于逆序对及频次统计只关心元素的相对大小（全序关系），不关心绝对数值，因此必须通过离散化将无限或巨大的值域收敛到严格的闭区间 $[1, N]$ 上。设离散化映射函数为 $\text{rank}(x)$，其数学性质必须满足：

$$A[i] < A[j] \iff \text{rank}(A[i]) < \text{rank}(A[j])$$

状态设计与算法推导

1. 逆序对统计的状态转移

状态空间定义为一个大小为 $N$ 的树状数组 tree[]，初始全为 $0$。算法执行流程：

1. 对原数组进行离散化，得到映射数组 R[i]。
2. 从 $1$ 到 $N$ 循环遍历 R[i]：
   • 首先查询当前权值树状数组中大于 R[i] 的元素个数：$\Delta = i - 1 - \text{Query}(R[i])$（其中 $i-1$ 为当前已插入的总元素量）。
   • 将 $\Delta$ 累加至全局答案 $ans$。
   • 将当前元素插入权值树状数组：$\text{Add}(R[i], 1)$。

2. 动态区间频次统计（多维偏序推导）

在更复杂的变形中，如统计区间内出现频次满足某种约束的元素数。通常利用无损差分思维或将查询拆分为动态离散事件。例如：统计满足 $A[i] \le A[j] + k$ 的二元组数量。状态转移方程的限界转化为：

$$\text{Query}(A[j] + k)$$

每次在遍历到 $j$ 时，瞬时框定可接纳的权值上界，利用 query 函数在 $O(\log N)$ 内切出合法的频次截面。

C++ 标准源码

以下是求解逆序对以及动态权值统计的完备 C++ 源码，包含了硬核的离散化预处理与严格的 long long 答案防溢出设计。

#include <iostream>
#include <vector>
#include <algorithm>

const int MAXN = 500005;

// 离散化辅助结构体
struct Element {
    int val;
    int id;
    // 严格弱序重载，若数值相同，必须保持原始位置顺序（稳定映射）
    bool operator<(const Element& other) const {
        if (this->val != other.val) return this->val < other.val;
        return this->id < other.id;
    }
};

struct TreeArray {
    int tree[MAXN];
    int size;

    void init(int n) {
        this->size = n;
        std::fill(tree, tree + size + 1, 0);
    }

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

    void add(int x, int val) {
        for (; x <= size; x += lowbit(x)) {
            tree[x] += val;
        }
    }

    int query(int x) const {
        int sum = 0;
        for (; x > 0; x -= lowbit(x)) {
            sum += tree[x];
        }
        return sum;
    }
};

Element a[MAXN];
int ranks[MAXN]; // 存储离散化后的权值排名（范围在 [1, n]）

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

    int n;
    if (std::cin >> n) {
        for (int i = 1; i <= n; ++i) {
            std::cin >> a[i].val;
            a[i].id = i;
        }

        // 离散化核心：利用标准库双字排序建立保序映射
        std::sort(a + 1, a + n + 1);
        for (int i = 1; i <= n; ++i) {
            ranks[a[i].id] = i; 
        }

        TreeArray bit;
        bit.init(n);

        long long inversion_cnt = 0; // 致命踩坑点：逆序对最大可达 O(N^2) 级别，必须锁死 long long 存储

        for (int i = 1; i <= n; ++i) {
            int curr_rank = ranks[i];

            // 查询当前权值树状数组中，排名在 [1, curr_rank] 的元素个数
            int smaller_or_equal = bit.query(curr_rank);

            // 致命踩坑点：i - 1 是当前已经插入树状数组的元素总数，减去不大于自己的，就是严格大于自己的数量
            inversion_cnt += (i - 1 - smaller_or_equal);

            // 将当前元素的频次打入权值树状数组
            bit.add(curr_rank, 1);
        }

        std::cout << inversion_cnt << "\n";
    }

    return 0;
}

NOIP 实战避坑指南

1. 离散化去重不当导致全序关系变形 在进行权值映射时，若原序列存在重复元素（如 5, 5, 2），选手在写离散化时若直接使用 std::unique 去重，会导致两个 5 映射到同一个权值下标。此时在树状数组中执行 i - 1 - query(curr_rank) 时，必须确保 query 统计的是“严格小于等于当前权值”的频次。若在排序比较算子中未将 id 作为次关键字，导致相同数值的相对顺序颠倒，会导致平局元素被错误地计入逆序对，直接引发 WA。
2. 计数器变量未用 long long 导致高位截断 对于 $N = 5 \times 10^5$ 的数据规模，最坏情况（完全逆序序列）下的逆序对总数为 $\frac{N(N-1)}{2} \approx 1.25 \times 10^{11}$。这个数字已经远远击穿了 32 位有符号整型 int 的最大承载量（$2.14 \times 10^9$）。如果 inversion_cnt 声明为 int，评测机在运行到大数据集时会发生算术高位溢出，导致最终结果截断、变负或呈现随机数，丢掉该测试点的全部全资分数。

经典 NOIP/洛谷 真题

1. 洛谷 P1908 逆序对

• 题意描述：给定一个长度为 $N$ 的序列，求其中逆序对的总数。
• 问题本质：标准的权值树状数组动态频次统计。
• 核心解题思路：此题为本节模板的直观映射。首先进行 $O(N \log N)$ 的离散化，将大值域收拢至 $[1, N]$。随后沿输入序列正向扫描，每次通过树状数组 $O(\log N)$ 查询前缀频次，差分得到大于当前值的历史元素数，累加进 long long 计数器，最后更新频次。

2. 洛谷 P5094 [USACO04OPEN] Moo Fest G / 踩踏

• 题意描述：有 $N$ 头牛，每头牛有坐标 $X_i$ 和听力阈值 $V_i$。两头牛 $i$ 和 $j$ 通信产生的能量消耗为 $\max(V_i, V_j) \times |X_i - X_j|$。求所有牛两两通信的能量总和。
• 问题本质：多维偏序约束下的拆项动态统计。
• 核心解题思路：
  • 排序破除 $\max$ 约束：将所有牛按照 $V_i$ 从小到大排序。这样当我们处理第 $i$ 头牛时，它与前方所有已处理的牛 $j$ 组合，$\max(V_i, V_j)$ 必然恒等于 $V_i$。问题转化为求 $V_i \times \sum_{j=1}^{i-1} |X_i - X_j|$。
  • 绝对值拆项维护：对于绝对值 $|X_i - X_j|$，根据坐标大小拆开：
    • 若 $X_j < X_i$，贡献为 $X_i - X_j$；
    • 若 $X_j > X_i$，贡献为 $X_j - X_i$。
  • 双树状数组对位解构：构建两个以坐标 $X$ 为下标的树状数组：BIT_count 维护当前坐标区间内的牛的数量，BIT_sum 维护当前坐标区间内牛的坐标之和。每次通过 query 动态获取前方坐标小于 $X_i$ 的牛的数量及坐标和，即可在 $O(\log N)$ 内算出当前牛对全局答案的阶乘级贡献。