树状数组

发表于

树状数组

image-20210419203504223

lowbit

lowbit（）函数用来取一个二进制最低位的一与后边的0组成的数

例：5（101），lowbit（5）=1（1）

​ 12（1100），lowbit（12）=4（100）

1
2
3
4
int lowbit(int t)
{
    return t&(-t);
}

原理，二进制数的负数是正数取反加一

12（1100），-12（0100）

求逆序数对

基本思想:开一个数组c[n+1],初始化为0，记录前面数据的出现情况;当数据a出现时，就令c[a]=1。这样的话，若求a的逆序数，只需要算出在当前状态下c[a+1,n]中有多少个1，因为这些位置的数在a之前出现且比a大。==复杂度O(n^2)==

树状数组的经典应用

另开一个==树状数组d[n+1]==,初始化为0，d[i]记录i结点所==管辖范围内==当前状态有多少个数;
当添加数据a时，就向上更新d数组,这样，当求a的逆序数时，只需要算sum(n)-sum(a)即可;

“区间修改+单点查询”的树状数组

基本思想：通过“差分”的方法（数组中记录的是每个元素与前一个元素的差），把问题转化为常规树状数组！

1
若原数组为a[i],设数组d[i]=a[i]-a[i-1](a[0]=0),则可以通过求d[i]的前缀和实现单点查询a[i]。

区间修改

当给区间[1,r]加上x的时候，a[1]与前一个元素a[l-1]的差增加了x，a[r+1]与a[r]的差减少了x。根据d[i]数组的定义，只需给d[l]加上x，给d[r+1]减去x即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//单点更新“差分”，为区间修改做准备(c是树状数组)
void add(int p,int x)
{
	while(p<=n)
	c[p]+=x,p+=p&-p;
}
//区间修改（通过两个端点的更新，实现区间修改的目的）
void range_add(int r,int x)
{
	add(l,x),add(r+1,-x);
}
//单点查询（因为差分，所以单点值即前缀和）
int ask(int p)
{
	int res=0;
	while(p)
	res+=c[p],p-=p&-p;
	return res;
}

“区间修改+区间查询”的树状数组

image-20210425202209068

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//维护2个树状数组
void add(int p,int x)
{
	for(int i=p;i<=n;i+=i&-i)
	c1[i]+=x,c2[i]+=x*p;
}
//区间修改（通过两个端点的更新，实现区间修改的目的）
void range_add(int r,int x)
{
	add(l,x),add(r+1,-x);
}
int range_ask(int l,int r)
{
    return ask(r)-ask(l-1);
}

B - Minimum Inversion Number

思路：

首先是怎么求其中一个序列的逆序数对

假设序列开始一个数都没有

每添加一个数之前计算序列有多少数大于该数（即在该位添加时会增加多少对逆序数）<===算作一个状态

将所有状态相加即是该序列的逆序数对数量

拿样例来说

img

当a0移动到an-1末尾后减少了它之后能与它形成逆序数对的个数(比它小的数)

​ 增加了在末尾时它之前能与它形成逆序数对的个数(比它大的数)

由于下一个循环数列必定是将头移至尾，所以减少的个数为比它小的个数，增加的个数为比它大的个数

因为数是不会重复的且为0~n-1共n个，所以 a[i] - 1就是序列中比它小的数的个数，n - a[i]就是序列中比它大的数的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int tree[6000],a[6000];
int n;

 int lowbit(int t)
{
    return t&(-t);
}
void add(int x,int d) {
    while(x<=n) {
        tree[x]+=d;
        x+=lowbit(x);
    }
}

int sum(int x) {
    int ans = 0;
    while(x>0) {
        ans+=tree[x];
        x-=lowbit(x);
    }

    return ans;
}

int main() {
    while(cin>>n) {
        int cnt=0;
        memset(tree,0,sizeof(tree));
        for(int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
            a[i]++;//树状数组从1开始 数据范围(0~n-1)
            cnt+=sum(n)-sum(a[i]);//找出所有比a[i]大的数的逆序数对数
            add(a[i],1);//记录这个数
        }

        int ans = cnt;
        for(int i=1;i<=n;i++) {
            cnt = cnt - a[i] + n - a[i] + 1;//比较完后因为 n 个数范围(0~n-1)且不重复， 所以比a[i] 小的数为a[i]-1;
             // 每次将头元素移至末尾都会减少比头小的数(a[i] - 1)个逆序数，增加比头大的数(n - a[i])个逆序数
             // 所以增加的逆序数为 n - a[i] * 2 + 1  [+(n - a[i]) -(a[i] - 1)]
            ans = min(ans,cnt);
        }

        printf("%d\n",ans);
    }

return 0;
}