树状数组——知识点

树状数组原理说明https://www.bilibili.com/video/BV1ce411u7qP/?spm_id_from333.1007.top_right_bar_window_history.content.clickvd_source9a638535989a48f74c7b938fa32bf477用于单点修改 前缀查询两者都要 O(log N) 的场景本质二进制模拟树状结构把前缀和拆成 log N 段每段长度 lowbit修改时从子节点到根节点查询时计算相关段。constintMAXN100005;intbit[MAXN];// 树状数组索引从 1 开始// 单点更新在位置 x 加上 vvoidadd(intx,intv){for(;xMAXN;xx-x)bit[x]v;}// 前缀查询查询 [1, x] 的和intsum(intx){intans0;for(;x0;x-x-x)ansbit[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; vectorint 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 中每个值的位置 vectorint 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; }