《树状数组》
首先来学习一下与偏序问题息息相关的持久化数据结构----树状数组（线段树也是，但这里我就不多说了）
想看详细原理证明，这是一个好博客：https://zhuanlan.zhihu.com/p/435561765
https://blog.csdn.net/a591027895/article/details/123951314
树状数组，其保存维护的值的数组是：c[]
通过上面的博客我们可以知道c[x]:表示区间[x-lowbit(x)+1,x]中，树状数组所维护的值
c[x]的父节点是：c[x+lowbit(x)]
c[x]的子节点是：c[x-1],c[x-1-lowbit(x-1)]......(直到【】里面的值到是0之间为止) a[x](a[]是原数组)
可以看出c[x]所代表的区间以x结尾，长度为lowbit(x),即：[x-lowbit(x)+1,x]
所谓的树状数组就是：
如果给定区间：[1,n]，原数组为a[1....n]
那么可以用c[1....n]来维护原数组的一些性质：如a[]某些性质的前缀和等
c[x],作为树状数组的节点可以由原数组a[x]和c[x-1],c[x-1-lowbit(x-1)].......这些节点组成
而c[x]本身也为c[x+lowbit(x)]，作出贡献（即其是子节点）
最终树状数组像这样：
其能干什么？
（1）.可以通过query（x）操作知道在区间[1,x]中，树状数组维护的值是多少（区间查询）
注意通过下面的操作，我们一定要保证我们知道要维护的区间的最小值为1
这个可以通过c[x]+c[x-lowbit(x)]+......来实现
因为c[x]代表范围：[x-lowbit(x)+1,x]
c[x-lowbit(x)]代表范围：[x-lowbit(x)-lowbit(x-lowbit(x)),x-lowbit(x)]
..............
这个范围应该可以看出是当组合起来的时候是连续的，最终组合成了区间[1,x]
ll query(int x)
{
ll ans = 0;
for (int i = x; i >= 1; i -= lowbit(i))
ans += c[i];
return ans;
}
（2）.可以通过add(x,k)操作，对c[x]的值进行k个单位修改（单点修改），同时可以向上传递修改的结果，即同时可以修改父节点
1 void add(int x, int k)
2 {
3 for (int i = x; i <= maxn; i += lowbit(i))
4 c[i] += k;
5 }
树状数组还可以实现区间修改和单点查询
这个的实现是靠利用差分，将区间修改，可以转化为两次单点修改
将单点查询，转化为了求区间的前缀和，即区间查询
《偏序问题》
好博客：https://zhuanlan.zhihu.com/p/112504092
以最经典的逆序对问题为例：
这里如果用最普通的想法要O（n^2）的时间复杂度，肯定会超时
这里的偏序关系是：i<j,ai>aj
如果满足这个关系,我们称（i，ai）
(j,aj)
解决这个问题我们可以用归并排序O（nlogn）
也可以用树状数组或线段树，思想都是一样的：
对于a，我们可以将其看作一个区间
我们按照顺序,从1~n，将a插入树状数组中，即add(a,+1),表示将c[a]+=1,代表区间[a-lowbit(a)+1,a]内数的个数增加了1
当我们插入到下标j时，天然地满足了下标小于j的下标对应的数都被插入到了树状数组中，
然后我们只要找一下此时有多少个数满足>aj，
即只要query(n)-query(aj),因为query(x),代表区间[1,x]中有多少个数
那么 query(maxa)-query(aj)就代表：【aj+1,maxa】有多少个数,即现在大于aj的有多少个数，这就是对于j来说的逆序对的个数
注意：因为这里a的数值巨大，但是N较小，我们可以进行离散化，来保证数组可以存储区间
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 5 * 1e5 + 5;
int a[N], c[N], n, maxn;
vector<int> sa;
int find(int x)
{
int l = 0, r = sa.size() - 1, ans;
while (l <= r)
{
int mid = (l + r) >> 1;
if (sa[mid] >= x)
{
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
return ans + 1;
}
int lowbit(int x)
{
return x & (-x);
}
void add(int x, int k)
{
for (int i = x; i <= maxn; i += lowbit(i))
c[i] += k;
}
ll query(int x)
{
ll ans = 0;
for (int i = x; i >= 1; i -= lowbit(i))
ans += c[i];
return ans;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
sa.push_back(a[i]);
}
sort(sa.begin(), sa.end());
sa.erase(unique(sa.begin(), sa.end()), sa.end());
maxn = sa.size();
ll ans = 0;
for (int i = 1; i <= n; i++)
{
int x = a[i];
int pos = find(x);
ans += (query(maxn) - query(pos));
add(pos, 1);
}
cout << ans;
return 0;
}
《进阶的逆序对问题》
标签：偏序,持久,树状,int,lowbit,数组,ans,区间,数据结构 From： https://www.cnblogs.com/cilinmengye/p/17008988.html