树状数组 逆序对

用大点节点C来表示小节点和的信息，这样我们可以进行快速的查询。

树状数组可以进行的操作：1.单点修改 2.区间查询 时间复杂度O(logn)

方法：新建一个数组 ci = a( i- lowbit(i)) + 1 到 ai 的 和

具体实现是二进制， 自己可以去查阅一下

查询操作：

ll query(int x)//求 1 ... x的和
{
  ll s = 0;
  for (; x; x -= x & (-x))	s += c[x];
  return s;
}

修改操作：

void modify(int x, ll s)// a[x] += s;
{
	for (; x <= n; x += x & (-x))
    	c[x] += s;
}

ok，现在我们可以来做例题了！

P3374 【模板】树状数组 1 

本题要求我们实行单点修改 和 区间查询， 注意不是[1, x]这个区间，而是[l, r]这个区间。由于我们的query查询的都是[1, x]这种的区间，根据前缀和的思想，用query(y) - query(x - 1)即可求出区间[x, y]的ans了

#include 
using namespace std;
 
#define x first
#define y second
#define endl '\n'
#define rep(i,a,n) for (int i = a; i < n; i ++ )
#define repn(i,a,n) for (int i = a; i <= n; i ++ )
#define pb push_back
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
 
ll gcd(ll a,ll b) { return b ? gcd(b,a % b) : a; }
const int mod = 1e9+7;
const int N = 500010;
int a[N];
ll c[N];
int n, q;
ll lowbit(ll x) { return x & (- x); }
 
ll query(int x)// 1 ... x的和
{
	ll s = 0;
	for (; x; x -= lowbit(x))	s += c[x];
 
	return s;
}
 
void modify(int x, ll s)// a[x] += s;
{
	for (; x <= n; x += lowbit(x))	c[x] += s;
}
 
int main()
{
	IOS;
	cin >> n >> q;
	for (int i = 1; i <= n; i ++ )
	{
		cin >> a[i];
		modify(i, a[i]);//给i的位置加上a[i]， 对树状数组来说 一开始是0麻
	}
	for (int i = 0; i < q; i ++ )
	{
		int ty;
		cin >> ty;
		if(ty == 1)
		{
			int x, d;
			cin >> x >> d;
			modify(x, d);//改成d, 那么 增量就是d - a[x]；
			a[x] += d;
		}
		else
		{
			int x, y;   cin >> x >> y;
			cout << query(y) - query(x - 1) << endl;
		}
	}
 
	return 0;
}

 P3368 【模板】树状数组 2

本题要求我们实现区间加， 也就是区间修改和单点查询。因为其实我们的树状数组是对前缀进行query， 所以我们进行单点查询的时候，我们怎么样才能得到一个单点的值呢???

假设我们是对差分数组进行建立树状数组， 那么我们查询出来的就不是一个前缀和了， 而是1个点的值了。这个应该很好理解。

同时，对差分数组建立了树状数组也满足了区间修改这个操作。我们知道差分数组中，修改[l, r]这个区间， 只需要q[l] +, q[r + 1] -， 即可。这里同理。 

#include 
using namespace std;
 
#define x first
#define y second
#define endl '\n'
#define rep(i,a,n) for (int i = a; i < n; i ++ )
#define repn(i,a,n) for (int i = a; i <= n; i ++ )
#define pb push_back
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
 
ll gcd(ll a,ll b) { return b ? gcd(b,a % b) : a; }
const int mod = 1e9+7;
const int N = 500010;
int a[N];
ll c[N];
int n, q;
ll lowbit(ll x) { return x & (- x); }
 
ll query(int x)// 1 ... x的和
{
	ll s = 0;
	for (; x; x -= lowbit(x))	s += c[x];
 
	return s;
}
 
void modify(int x, ll s)// a[x] += s;
{
	for (; x <= n; x += lowbit(x))	c[x] += s;
}
 
int main()
{
	IOS;
	cin >> n >> q;
	for (int i = 1; i <= n; i ++ )
	{
		cin >> a[i];
		modify(i, a[i] - a[i - 1]);//给i的位置加上a[i]， 对树状数组来说 一开始是0麻
	}
	for (int i = 0; i < q; i ++ )
	{
		int ty;
		cin >> ty;
		if(ty == 1)
		{
			ll l, r, d;
			cin >> l >> r >> d;
			modify(l, d);
			modify(r + 1, -d);
		}
		else
		{
			int x;
			cin >> x;
			cout << query(x) << endl;
		}
	}
 
	return 0;
}

P1908 逆序对 

问题本来是要求 i < j 且 ai > aj这个静态问题变成动态问题！    类似扫描线

for j = 1 ~ n
    统计 a1 ~ aj-1 里  > a[j]

问题转化为：我们要维护一个数据结构，数据结构d里面存了a1~aj-1,我们要统计d里有多少个数字大于a[j]，做完将aj加入
2.权值开树状数组

现在数据结构D：1.加入一个数    2.统计>aj的数

那么什么叫对权值开树状数组， 比如加入了一个数字x, 那么就d[x] += 1;
那么当比如问多少个大于aj, 就是统计aj后面1的个数 ans += D[j]; 后缀和查询
那么查后缀我们可以将ai -> n + 1 - ai，那么后缀和就变成了前缀和
等于将1-n反转成n-1，这样就实现了后缀和变成了前缀和

PS:我们代码没有离散化哦！ 过不了

#include 
#include 
#include 
#include 
#include 
#include 
 
 
using namespace std;
 
#define x first
#define y second
#define endl '\n'
#define rep(i,a,n) for (int i = a; i < n; i ++ )
#define repn(i,a,n) for (int i = a; i <= n; i ++ )
#define pb push_back
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
 
ll gcd(ll a,ll b) { return b ? gcd(b,a % b) : a; }
const int mod = 1e9+7;
const int N = 500010;
ll lowbit(int x)	{ return x & (-x);}
int a[N];
ll c[N];
int n;
ll ans;
 
ll query(int x)
{
	ll s = 0;
	for (; x; x -= lowbit(x))
		s += c[x];
 
	return s;
 
}
void modify(int x, ll s)
{
	for (; x <= n; x += lowbit(x))	c[x] += s;
}
 
 
int main()
{
	IOS;
	cin >> n;
	for (int i = 1; i <= n; i ++ )
	{
		cin >> a[i];
		a[i] = n + 1 - a[i]; 
	}
 
	for (int i = 1; i <= n; i ++ )
	{
		ans += query(a[i]);
		modify(a[i], 1);
	}
	cout << ans << endl;
 
	return 0;
}

 PS：贴一份别人的正确代码

#include 
using namespace std;
#define int long long 
const int N = 5e5+10;
int a[N], c[N];
 
vector<int> v;//离散化
map<int, int> p;
int n;
 
int query(int x)
{
    int res = 0;
    for(; x ;x -= x & (-x)) res += c[x];
    return res;
}
 
void insert(int x)
{
    for(;x <= n;x += x&(-x)) c[x] ++;
}
 
 
signed main()
{
    cin >> n;
    
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        v.push_back(a[i]);
    }
    // 离散化
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(int i = 0; i < v.size(); i ++)
    {
        p[v[i]] = i + 1;
    }
    
    int ans = 0;
    
    for(int i = 1; i <= n; i ++)
    {
        insert(p[a[i]]);
        // 累加结果即可
        ans += i - query(p[a[i]]);
    }
    
    cout << ans << endl;
    
    return 0;
}
/*
i - query(a[i]) 可以得到比a[i]大的数的个数。
query(a[i]) - mp[a[i]] 可以得到比a[i]小的个数。 
这里mp[a[i]]表示离散化之后a[i]有几个。
*/