树状数组——知识点

树状数组

原理说明

https://www.bilibili.com/video/BV1ce411u7qP/?spm_id_from=333.1007.top_right_bar_window_history.content.click&vd_source=9a638535989a48f74c7b938fa32bf477

用于：单点修改 + 前缀查询，两者都要 O(log N) 的场景
本质：二进制模拟树状结构，把前缀和拆成 log N 段，每段长度 = lowbit，修改时从子节点到根节点，查询时计算相关段。

constintMAXN=100005;intbit[MAXN];// 树状数组，索引从 1 开始// 单点更新：在位置 x 加上 vvoidadd(intx,intv){for(;x<MAXN;x+=x&-x)bit[x]+=v;}// 前缀查询：查询 [1, x] 的和intsum(intx){intans=0;for(;x>0;x-=x&-x)ans+=bit[x];returnans;}

模板题

逆序对计数

本质根据B求A的逆序数

#include <bits/stdc++.h> using namespace std; // 树状数组求逆序对 const int MAXN = 100005; int bit[MAXN]; void add(int x, int v) { for (; x < MAXN; x += x & -x) bit[x] += v; } int sum(int x) { int s = 0; for (; x > 0; x -= x & -x) s += bit[x]; return s; } int main() { int n; cin >> n; vector<int> A(n), B(n); for (int i = 0; i < n; i++) cin >> A[i]; for (int i = 0; i < n; i++) cin >> B[i]; // 记录 B 中每个值的位置 vector<int> pos(n + 1); for (int i = 0; i < n; i++) pos[B[i]] = i + 1; // 位置从 1 开始，方便树状数组 // 求 C 的逆序对数 long long ans = 0; for (int i = 0; i < n; i++) { int target = pos[A[i]]; // 已出现i个数,减去小于等于 target 的元素个数,就是逆序个数 ans += i - sum(target); add(target, 1); } cout << ans << endl; return 0; }