目录
树状数组与线段树：
lowbit(x)
单点更新+区间修改
单点更新：
区间查询
洛谷：树状数组模板题1：
单点查询+区间修改：
洛谷：树状数组模板题2：
维护区间最大值的单点更新+区间查询(比较复杂)：
单点更新：
代码：
区间查询：
代码：
HDU 1754
区间查询+区间修改：
利用树状数组求解逆序数：
图片来源：bestsort.cn
树状数组和线段树复杂度一样，查询更新为O(logn)，树状数组比线段树的代码简洁，巧妙利用二进制lowbit(x)(表示x的二进制最右边的1)。但是线段树能解决的树状数组未必可以解决，树状数组可以解决的线段树一定可以解决。
如何取出二进制的1，对于一个二进制…..1….00..0(1前面是0或1，1后面全部是0)，得到这个1，可以想到移位，但是又要循环到1。寻找更优化的复杂度，对每一位取反再相与全部为0，怎么样让那个1取反仍然是1，1后面的取反是什么都无所谓。那么对取反后的(….1111.1111)加1操作就变成了(…..1..00..0)也就是该1前面的全取反，该1后面的全不变，包括它自己。这样相与就得到了最低位1代表的值。取反+1又是补码，也就是x与它的相反数相与，即x&(-x)。
所以代码为：
int lowbit(x){ return x&(-x);
}
网图:
规定一个结点的上一个结点，即父节点为x+lowbit(x)。
所以对于单点修改来说(下面以区间和为例)
void update(int x,int k){ for(;x <= n;x+=lowbit(x)) t[x]+=k; }既然这样规定，那么一个结点所代表的数的个数为最低为1二进制的权值，比如…10只能由….01相加lowbit而来，加上本身所以为2。…100可由…010和….011（2+1+1=4）。…10…0(n个0)可由…01…0(2^n-2)…001…0(2^n-3) 一直到……1(1)等比数列求和公式可得2^n-1+1（本身）。(有递归的感觉)
所代表的数组范围也就是(x-lowbit(x)+1,x)
所以对于区间查询来说：
int getsum(int x){//-lowbit(x)原因就是它对应结点所代表的大小，在计算除去它代表 int ans = 0;//结点的个数就行了。 for(;x;x-=lowbit(x)) ans+=t[x]; return ans; }注意，这时候得到的是[1,x]的getsum(为了更快，不用因为l在某t内二拆分)。求[x,y]利用
getsum(y)-getsum(x-1)得到。
对于区间修改，如何修改。在线段树中我们用一个add来记录，在这里我们用一个算法——差分。何为差分,就是利用一个数组记录该下标与该下标的上一个元素在原数组中的差值，这样只需要修改端点处即可。这样理解，比如对[x,y]做+k操作，我们就让div[x]+=k,div[y+1]-=k；在x之前的不受影响，是原来的，在[x,y]之间的会有①，对于大于y的有②。
a[n]=a[n]+div[1….n]=a[n]+div[x]=a[n]+k;①
a[n]=a[n]+div[1….n]=a[n]+div[x]+div[y+1]=a[n]+k-k=a[n];②
这样，对于a[i]只要是求的差分数组的前i项和与a[i]相加即可。转化为更新差分数组和求差分数组前i项和。所以将t作为差分数组即可；
对于一个数组a[x]更新，那么要重算x之后的包括x的所有数组值。
外层for循环毫无疑问，就是更新x之后的所有t数组值。如何更新呢，之前所讲：
…10…0(n个0)可由…01…0(2^n-2)(数2^n-2)…001…0(2^n-3)(数x-2^n-3) 一直到……1(1)(数x-1)；
也就有了内层for循环，每个for复杂度O(logn)，所以复杂度为O((logn))^2，不算太高。
区间查询不能像sum一样相减了，只能精确定位。
之前说过，对于一个t[x]，所代表的范围为[x-lowbit(x)+1,x]；
如果l <= r-lowbit(r)+1 ans=ans(ans,t[r]){因为t[r]里面的代表的元素都在[l,r]区间内}
如果l>r-lowbit(r)+1 ans=ans(ans,a[r]),r--;{因为t[t]里面代表的元素有不是[l,r]的，不可以直接运用，所以需要拆分}
利用差分进一步修改，上一个差分数组初始化0，这次初始化赋值div[i]=a[i]-a[i-1];
其实就是求差分数组的前缀和的前缀和，比如[1,x]就是求的a[x]到a[1]的和,
a[i]=j＝1idiv[j]
构建两个树状数组t1[],t2[]; t1[x]=d[x],t2[x]=d[x]*i；
void add(int x,int k){ y=x; for(;x<=n;x+=lowbit(x)) t1[x]+=k,t2[x]+=y*k; return ; } void range_add(int l,int r,int x){ add(l,x);add(r+1,-x); } int getsum(int x){ int ans = 0,y=x; for(;x;x-=lowbit(x)) ans +=((y+1)*t1[x]-t2[x]); return ans; } int range_getsum(int l,int r){ return getsum(r)-getsum(l-1); }遍历一遍，查询x之前有多少个数，那么i-number就是在i后面的数(因为getsum包含自己，所以不需要加一)。
#include<algorithm> #include<iostream> #include<cstring> #include<string> #include<cstdlib> #include<map> #include<cmath> #include<vector> #include<cstdio> /* 在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。 一个排列中逆序的总数就称为这个排列的逆序数。比如一个序列为4 5 1 3 2， 那么这个序列的逆序数为7， 逆序对分别为(4, 1), (4, 3), (4, 2), (5, 1), (5, 3), (5, 2),(3, 2)。 输入描述: 第一行有一个整数n(1 <= n <= 100000), 然后第二行跟着n个整数，对于第i个数a[i]，(0 <= a[i] <= 100000)。 */ using namespace std; typedef long long ll; const int maxn = 1e6+50; int t[maxn<<4]; int n,a; int lowbit(int x){ return x&(-x); } void update(int x,int k){ for(;x<=n;x+=lowbit(x)) t[x]+=k; } int getsum(int x){ int ans = 0; for(;x;x-=lowbit(x)) ans+=t[x]; return ans; } inline int read(){ int f = 1,number = 0; char c = getchar(); while(c>'9'||c<'0'){ if(c=='-') f=-1; c=getchar(); } while(c<='9'&&c>='0'){ number = number*10+c-'0'; c=getchar(); } return number*f; } int main(){ ll ans = 0; while(cin>>n){ memset(t,0,sizeof(t)); for(int i = 1;i <= n;i++){ a=read(); update(a,1); ans += (ll)(i-getsum(a)); } cout << ans << endl; } return 0; }求逆序数方法还有归并排序，在另一篇文章里面细讲：
#include<algorithm> #include<iostream> #include<cstring> #include<string> #include<cstdlib> #include<map> #include<cmath> #include<vector> using namespace std; typedef long long ll; const int maxn = 1e6+50; ll a[maxn]; ll b[maxn]; ll ans; void _merge(int l,int mid,int r){ int p1 = l,p2 = mid+1; for(int i = l;i <= r;i++){ if(((a[p1] <= a[p2])||(p2 > r))&&p1<=mid){ b[i] = a[p1++]; }/*等号无所谓，这里为了求逆对数，相等的情况让前面的先进去，主要靠后面进行求逆对数 */ else { b[i] = a[p2++]; ans += (ll)(mid-p1+1); } } for(int i = l;i <= r;i++) a[i] = b[i]; return ; } void erfen(int l,int r){ int mid = (l+r)>>1; if(l < r){ erfen(l,mid); erfen(mid+1,r); } _merge(l,mid,r); return ; } int main(){ int n; cin >> n; for(int i = 0;i < n;i++) cin >> a[i]; ans = 0; erfen(0,n-1); cout << ans << endl; return 0; }如果有题说大致每次置换某一区间，求每一次对应的逆序对的奇偶性，这时候不要”傻乎乎”的每次计算，利用性质：每一对调换奇偶性改变。
