博客

线段树是一类非常有用的数据结构 这个可以体现到求解一组序列的逆序数上来

可以这么想 我们求逆序数的时候，对于每一个数字都找前面比他大的数字的数目

例如 9 5 7 9这三个序列 我们先找5前面比5大的数字的个数 很明显是9 有一个

我们继续找7前面比7大的个数 也是9

找 9 前面比9大的个数 和明显没有

按照这个想法实现的是O(n^2)的一个算法 复杂度不是很好

既然是区间操作 我们想到了线段树

我们先建立一个空树 然后呢 按照这个序列的顺序将每个值插入 ，每次插入伴随一次查询 查询前面插入的比这次插入的大的数字的个数

然后就可以了 复杂度 nlogn 可以接受

需要注意 ：1.很多时候可能要离散化 这个很容易想 因为如果数字是long long 类型以及以上的那么空间就爆了

2.注意建立空树的时候要在 1-n+1上建立空树 因为有可能查询n query（1，n+1，n）的时候就出错了 这样并不影响结果，仔细体会一下

下面这是没有离散的代码

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxn = 1e5+10;
int arr[maxn];
struct node{int sum,l,r;};
node segtree[4*maxn];
int fa[maxn];
void buildtree(int num,int l,int r)
{
    if(l==r)
    {
        segtree[num].l=segtree[num].r=l;
        fa[r]=num;
        segtree[num