Hexo
0%

树状数组

Posted on In ,
Symbols count in article: 3.3k Reading time ≈ 3 mins.

树状数组基础

树状数组是线段树的简化版，可以做到：1.单点修改，单点查询，2.区间修改，单点查询，3.区间查询，区间修改

树状数组的构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n;
int a[1005],t[1005]; //对应原数组和树状数组

int lowbit(int x){//计算一个非负整数n在二进制下的最低为1及其后面的0构成的数
    return x&(-x);
}

void add_dandian(int x,int k)//用于更新每一个节点的状态
{
	for(int i=x;i<=n;i+=lowbit(i))
	t[i]+=k;
}


  • 单点修改，区间查询

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int add_dandian(int x,int k)//用于更新每一个节点的状态
    {
    	for(int i=x;i<=n;i+=lowbit(i))
    	t[i]+=k;
    }

    int ask(x){//查询前x项区间
    	int sum = 0;
    	for(int i=x;i;i-=lowbit(i)){
    		sum+=t[i];
    	}
    	return sum;
    }


​ 通过图中不难看出，sum[7]=t[7]+t[6]+t[4] ,我们进一步发现,6=7-lowbit(7),4=6-lowbit(6)，所以我们可以通过不断的- lowbit操作来实现求和

  • 求特定l到r区间(利用前缀和计算)
1
2
3
4
5
6
7
8
9
10
int search(int L,int R)
{
	int ans = 0;
	for(int i=L;i;i-=lowbit(i))
	ans+=c[i];
	for(int i=R-1;i;i-=lowbit(i))
	ans-=c[i];
	return 0;
}

  • 区间修改，单点查询

    我们需要构造出原数组的差分数组b，然后用树状数组维护b数组即可

    对于区间修改的话，我们只需要对差分数组进行操作即可，例如对区间[L,R]+k,那么我们只需要更新差分数组add(L,k),add(R+1,-k)，这是差分数组的性质.

1
2
3
4
5
6
7
8
9
int update(int pos,int k)//pos表示修改点的位置,K表示修改的值也即+K操作
{
	for(int i=pos;i<=n;i+=lowbit(i))
	c[i]+=k;
	return 0;
}
update(L,k);
update(R+1,-k);

单点查询:

求出b数组的前缀和即可，因为a[x]=差分数组b[1]+b[2]+…+b[x]的前缀和，

1
2
3
4
5
6
7
ll ask(int pos)//返回区间pos到1的总和
{
	ll ans=0;
	for(int i=pos;i;i-=lowbit(i)) ans+=c[i];//注意b数组是数组数组，树状数组求前缀和不是全部加起来
	return ans;
}

区间修改，区间查询：

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
# include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
#define ll long long 
ll int n,f,t1[maxn],t2[maxn],c[maxn];//t1,t2都为前缀数组

int lowbit(int k)
{
  return k&(-k);
}

void add_dandian(ll int k,ll int p)
{
  for(int i=k;i<=n;i+=lowbit(i))
  {
    t1[i]+=p;
    t2[i]+=p*k;//记得乘k而不是i
  }
}

ll int search(ll int k)
{
   ll int sum=0;
  for(int i=k;i;i-=lowbit(i))
  {
    sum+=(k+1)*t1[i]-t2[i];//是乘k+1
  }
  return sum;
}

int main()
{
    cin>>n>>f;
    c[0]=0;
    for(int i=1;i<=n;++i)
    {
      cin>>c[i];
      add_dandian(i,c[i]-c[i-1]);//差分数组建立树状数组
    }
    for(int i=1;i<=f;++i)
    {
        int l,r,k;
        cin>>l>>r>>k;
        add_dandian(l,k);//修改
        cout<<search(r)-search(l-1)<<endl;//查询
    }
}

逆序对

给定的一段正整数序列 A，逆序对就是序列中 Ai > Aj 且 i < j 的有序对，输出 A 中逆序对总数目。

离散化就是另开一个数组, d[i]用来存放第i大的数在原序列的什么位置，比如原序列a={5，3，4，2，1}，第一大就是5，他在a中的位是1，所以d[1]=1，同理d[2]=3，········所以d数组为{1，3，2，4，5}，转换之后，空间复杂度就没这么高了，但不是求d中的逆序对了，而是求d中的正序对

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
54
55
56
57
58
# include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int n,d[maxn]//用来存放第i大的数在原序列的什么位置
int,tree[maxn];
struct node{
  int id;//初始位置
  int val;//值
  bool operator<(const node &a) const{//升序排序
    if(val==a.val)
    return id<a.id;//让原顺序先出现（即逆序靠后出现）的相对值更小，防止离散后逆序遍历时错误地统计到相等值对
    return val<a.val;
  }
}t[maxn];

int lowbit(int x)
{
  return x&(-x);
}

void add_dandian(int x)
{
  for(int i=x;i<=n;i+=lowbit(i))
  {
    tree[i]++;
  }
}

int search(int x)
{
  int sum=0;
  for(int i=x;i;i-=lowbit(i))
  {
    sum+=tree[i];
  }
  return sum;
}
int main()
{
  cin>>n;
  for(int i=1;i<=n;++i)
  {
     cin>>t[i].val;
     t[i].id=i;
  }
  sort(t+1,t+1+n);//此时的数组t的每一个值从小到大排列
  for(int i=1;i<=n;++i)
  {
    d[i]=t[i].id;//d[i]表示第i大的数的id
  }
  long long int sum=0;//开ll防爆
   for(int i=n;i>0;--i)//从后往前遍历，所以每一个数能找的都是比他大的数，那么找比每一个数的id还小的个数就好了，也就是tree[i]的前缀和(注意要去掉本身)
   {
    sum+=search(d[i]-1);
    add_dandian(d[i]);
   }
   cout<<sum<<endl;
}