[toc]

什么是树状数组

顾名思义就是一个结构为树形结构的数组，于二叉树的结构类似但又不同，它是在二叉树的结构上删除了一些中间节点。

树状数组的结构：

• 数组A： 传入数据的原数组
• 数组C：建立起来的树状数组

前置知识—lowbit(x)运算

如何计算一个非负整数n在二进制下的最低为1及其后面的0构成的数？ 例如：44 = 101100，最低为1和后面的0构成的数是100 = 4

所以lowbit(44) = 4

lowbit运算时怎么实现?

44的二进制=(101100) ，-44的二进制=(010100)，然后我们把44和-44的二进制进行按位与运算，也即按位&得到,二进制000100，也就是十进制的4。

int lowbit (int x)
{
	return x & -x ;//返回 x 的最后一位 1 
}

树状数组结构分析

所以lowbit(x) = x&(-x)

通过观察节点的二进制数，进一步发现，树状数组中节点x的父节点为x+lowbit(x),例如t[2]的父节点为t[4]=t[2+lowbit(2)]

单点修改，区间查询

所以我们在单点修改的同时，更新父节点就变得尤为简单，，例如我们对a[1]+k，那么祖先节点t[1],t[2],t[4],t[8]都需要+k更新(因为t[]表示前缀和)，此时我们就可以用lowbit操作实现。

int add_dandian(int x,int k)
{
	for(int i=x;i<=n;i+=lowbit(i))
	t[i]+=k;
}

实现区间查询

例：我们需要查询前7项的区间和sum[7]

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

区间 [1, x] 上的和

int query(x){
	int sum = 0;
	for(int i=x;i>=1;i-=lowbit(i)){
		sum+=t[i];
	}
	return sum;
}

区间[x, y] 上的区间和即为 query(y) - query(x - 1) (前缀和思想)

int search(int x,int y)
{
	int ans = 0;
	for(int i=x-1;i;i-=lowbit(i))
	ans-=c[i];
	for(int i=y;i;i-=lowbit(i))
	ans+=c[i];
	return 0;
}

区间修改，单点查询

对于这一类操作，我们需要构造出原数组的差分数组c，然后用树状数组维护c数组即可

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

void update(int pos,int k)//pos表示修改点的位置,K表示修改的值也即+K操作
{
	for(int i=pos;i<=n;i+=lowbit(i))
	c[i]+=k;
}
update(L,k);
update(R+1,-k);

对于单点查询操作，求出c数组的前缀和即可，因为a[x]=差分数组c[1]+c[2]+…+c[x]的前缀和，这是差分数组的性质之一。

ll ask(int pos)//返回区间pos到1的总和
{
	ll ans=0;
	for(int i=pos;i>=1;i-=lowbit(i)) ans+=c[i];
	return ans;
}

例子：洛谷P1908 逆序对

#include<bits/stdc++.h>

#define int long long
using namespace std;

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

typedef pair<int, int> pii;

int n;
pii a[500005];
int c[500005]; //初始时树状数组每个节点均为0

int query(int x) { //向前查询比x值大的个数
    int s = 0;
    while (x) {
        s += c[x];
        x -= lowbit(x);
    }
    return s;
}

void modify(int x, int y) {
    while (x <= n) {
        c[x] += y;
        x += lowbit(x);
    }
}

signed main() {
    int ans = 0;
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>a[i].first;
        a[i].second = i;
    }
    //离散化：安值从大到小排序，若值相同，则按位置从大到小排序  保证相同的值不会统计为逆序数
    sort(a + 1, a + 1 + n, greater<pii>());

    for (int i = 1; i <= n; i++) {
        ans += query(a[i].second);
        modify(a[i].second, 1); //对x位置及后续位置做加1的操作，即x位置的数对后续位置的贡献
    }
    cout << ans << '\n';
    return 0;
}

/**
原数据：5 4 2 6 3 1 降序后：6 5 4 3 2 1
      1 2 3 4 5 6       4 1 2 5 3 6
*/