树状数组

学了一波树状数组

非常好写

inline int lowbit(int x){return x&(-x);}
inline void add(int x,int d){while(x<=n)c[x]+=d,x+=lowbit(x);}
inline ll query(int x){ll res=0;while(x)res+=c[x],x-=lowbit(x);return res;}  

支持两种操作：

单点+=c

查询前缀和

POJ2299  树状数组求逆序对+离散化

这里的c[x]代表数字出现次数的前缀和

在j∈(1，i)区间里找a[i]>a[j]的个数  边找边更新ans即可

//#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const int maxn=5e4+5;
int n;
vector<int>v;
int a[500005];
int b[500005];
int c[500005];
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int d){while(x<=n)c[x]+=d,x+=lowbit(x);}
inline ll query(int x){ll res=0;while(x)res+=c[x],x-=lowbit(x);return res;}  
inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;	
} 


void setid(int n)
{
	sort(++v.begin(),v.end());
	v.erase(unique(++v.begin(),v.end()),v.end());
}
int getid(int x){return lower_bound(++v.begin(),v.end(),x)-v.begin();}
int main()
{
	while(~scanf("%d",&n))
	{
		
	 	if(n==0)break;
		v.clear(); 
		v.resize(n+1);
		memset(c,0,sizeof(c));
	 	for(int i=1;i<=n;i++)
	 	{
	 		a[i]=read();
			v[i]=a[i];
			//b[i]=i;		 	
		}
		setid(n);
		ll ans=0;
		for(int i=1;i<=n;i++)
		{
			add(getid(a[i]),1);
			ans+=1ll*(i-query(getid(a[i])));
		}
		printf("%I64d\n",ans);
	} 
}
 

hdu1166  树状数组模板题

区间查询加法和，单点更新+=c

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=5e4+5;
int n;int c[maxn];
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int d){while(x<=n)c[x]+=d,x+=lowbit(x);}
inline ll query(int x){ll res=0;while(x)res+=c[x],x-=lowbit(x);return res;}  


int main()
{
	int T;int kase=0;
	cin>>T;
	while(T--)
	{
		scanf("%d",&n);int k;
		memset(c,0,sizeof(c));
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&k);
			add(i,k);
		}
		printf("Case %d:\n",++kase);	
		char s[8];int ql,qr;
		while(1)
		{
			scanf("%s",&s);
			if(s[0]=='E')break;
			if(s[0]=='Q')
			{
				scanf("%d %d",&ql,&qr);
				printf("%d\n",query(qr)-query(ql-1));
			}
			if(s[0]=='A')
			{
				scanf("%d %d",&ql,&qr);
				add(ql,qr);
			}
			if(s[0]=='S')
			{
				scanf("%d %d",&ql,&qr);
				add(ql,-qr);
			}
		}
	}
}