树状数组
先来介绍树状数组的运作方式，设原有数组为A，现在我们要做的时对A的某个区间进行求知(求和，最大最小值，或其他)，以及对某个单点进行修改，或某个区间进行修改等等操作，在用朴素算法时会消耗大量时间，用树状数组和线段树可以在短时间内解决问题，树状数组可以解决的问题，线段树都可以解决，但构造线段树会消耗很多时间，对于大多数区间操作题目，使用树状数组可以更快的解决问题，而且代码也很少。，，，，但是相对来说功能还是受到限制的。
树状数组C中C[i]的值为以i结尾的lowbit(i)个长度的区间内的目标值(求和，最大最小值，或其他)，那么我们要求从i到0之间的所有数的和，只需要计算当前的C[i]值，然后一直减去lowbit(i)即可。一个很大的数也可以在logn次lowbit内表示出来。lowbit(i)的值为i的二进制数中，从低位到高位，第一个连续0的个数，lowbit(i) = 2^k，k = 第一个连续0的个数。比如i=18=10010(2)的第一个连续0的个数为1，而不是2，则lowbit(i) = 2。
设A为原始数组，C为树状数组。
C[1] = A[1];
C[2] = A[2] + A[1];
C[3] = A[3];
C[4] = A[4] + A[3] + A[2] + A[1];
C[5] = A[5];
C[6] = A[6] + A[5];
C[7] = A[7];
C[8] = A[8] + A[7] +...+ A[2] + A[1];
即C[i]所覆盖的区间为以i结尾的长度为lowbit的区间，若我们现在要计算sum(A[1]-A[7])，那么i从7开始，先加上C[7]，然后i -= lowbit(i)，此时i=6，加上C[6]，再减去lowbit(i)，此时i为4，加上C[4]，减去lowbit7(i)后，i为0，计算结束，A[1]-A[7]内的数都只被计算了一次。
在上述计算过程中，共迭代了3次，7，6，4，然后就是0了。那当我们要计算一个很大的数时，比如100w，迭代的次数会不会很大呢？当然不会，再大也会在logn次内完成迭代。
我们来分析一下具体的迭代过程，在上述i=7时，7的二进制数为111，i = 2^2+2^1+2^0，而在迭代过程中，我们发现三次lowbit(i)的值恰好就是2^0、2^1、2^2，这就是树状数组的神奇之处，利用二进制数建立起来的。那我们知道任何一个正整数都可以唯一表示成一些2的幂的和，且这些幂的个数一定不会超过logn(从二进制数看，最多也就logn个1)。因此使用树状数组可以很快的求解区间问题。时间复杂度O(logn)，相比线段树，树状数组构造起来简单，且高效。
构造最简单的树状数组
设数组c，c[i]的值为以i结尾的lowbit(i)个长度的区间内的目标值(求和，最大最小值，或其他)，若要会用仅仅知道这个就够了。
对于某个点i，包含i的点有i,i+lowbit(i),i+lowbit(i)+lowbit(i+lowbit(i))+lowbit(..)一直递归下去，直至最右端。 lowbit(i) = i&(-i);
所以再构造树状数组时，代码很简单。
void update(int i,int k,int N){ //k为要修改的值，可正可负
while (i<=N){
c[i] += k;
i += lowbit(i);
}
return;
}求1-i区间内的和,,这里要充分理解c[i]的作用范围是以i结尾的，长度为lowbit(i)的区间。
int query(int i){
int ans = 0;
while (i){
ans += c[i];
i -= lowbit(i);
}
return ans;
}模板题 HUD1166
题意：给出N个数，每次操作有增加某个点的值，减少某个点的值，求某个区间内的和。
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 5e4+5;
int c[maxn];
char s[20];
inline int lowbit(int i){return i&(-i);}
void update(int i,int k,int N);
int query(int i);
int main(){
int T,N,cases = 0,temp,x,y;
scanf ("%d",&T);
while (T--){
printf ("Case %d:\n",++cases);
memset(c,0,sizeof c);
scanf ("%d",&N);
for (int i=1;i<=N;i++){
scanf ("%d",&temp);
update(i,temp,N);
}
while (1){
scanf ("%s",s+1);
if (s[1]=='E') break;
scanf ("%d %d",&x,&y);
if (s[1]=='A') update(x,y,N);
else if (s[1]=='S') update(x,-y,N);
else printf ("%d\n",query(y)-query(x-1));
}
}
return 0;
}
void update(int i,int k,int N){
while (i<=N){
c[i] += k;
i += lowbit(i);
}
return;
}
int query(int i){
int ans = 0;
while (i){
ans += c[i];
i -= lowbit(i);
}
return ans;
}接下来讨论较复杂的问题
对于区间的操作大致可分为4大类。
1.单点更新，单点查询
2.单点更新，区间查询
3.区间更新，单点查询
4.区间更新，区间查询
其中1用传统数组就可解决，2上面已经讨论。下面看3，4
区间更新，单点查询
在原数组A的基础上，构建一个差分数组D，D[i] = A[i]-A[i-1]，那么，A[i]的值就是D数组的前i个数的和，我们在D数组上建立树状数组即可。对于每次更新，例如在[x,y]区间内加减一个常数值，D[x+1~y]的值是不变的，只需更改D[x]和D[y+1]的值就好。
那么这种情况下，树状数组c是建立在差分数组D上的，每次更新区间值，要更新D[x]和D[y+1]的值。代码与第2种情况的完全相同。
每次更新和查询的时间复杂度都为O(logn).
for (rint i=1;i<=N;i++){
scanf ("%d",&A[i]);
D[i] = A[i] - A[i-1];
update(i,D[i]);
}
//只是原数组从A[]变成了差分数组D[]，updae和query函数和上面一模一样区间更新，区间查询
在3中，我们知道查询数组A中单点值时，是差分数组的1-i的和，那要查询数组A的前i个数的和呢？当然就是差分数组D中前i的数的所有前缀和的和。那么最后算下来，D[1]被加了i次，D[2]被加了i-1次...D[i]被加了1次。
可以进行如下表示
A[1]+A[2]+...+A[i] =D[1]*i+D[2]*(i-1)+...+D[i]*1
= (D[1]+D[2]+...+D[i])*i-(D[1]*0+D[2]*1+...D[i]*(i-1))
即我们还需要再建立一个树状数组C2[]，目标值为D[i]*(i-1).
update函数需要更新一下
void update(int i,ll k){
ll temp = k*(i-1);
while (i<=N){
c1[i] += k;
c2[i] += temp;
i += lowbit(i);
}
return;
}拿来两道板子题
洛谷P3368 区间更新，单点查询
POJ3468 区间更新，区间查询
洛谷P3368 区间更新，单点查询
inline效果挺明显的，register int用了反倒慢了一些？？
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
#define rint register int
const int maxn = 5e5+5;
int A[maxn],D[maxn],c[maxn];
int N,M;
inline int lowbit(int i){return i&(-i);}
inline void update(int i,int k){
while (i<=N){
c[i] += k;
i += lowbit(i);
}
return;
}
inline int query(int i){
int ans = 0;
while (i){
ans += c[i];
i -= lowbit(i);
}
return ans;
}
int main(){
int x,y,k,flag;
scanf ("%d %d",&N,&M);
for (rint i=1;i<=N;i++){
scanf ("%d",&A[i]);
D[i] = A[i] - A[i-1];
update(i,D[i]);
}
while (M--){
scanf ("%d",&flag);
if (flag==1){
scanf ("%d%d%d",&x,&y,&k);
D[x] += k,D[y+1] -= k;
update(x,k); update(y+1,-k);
continue;
}
scanf ("%d",&x);
printf ("%d\n",query(x));
}
return 0;
}POJ3468 区间更新，区间查询
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
ll a1[maxn],D[maxn],c1[maxn],c2[maxn];
int N,Q;
inline int lowbit(int i){return i&(-i);}
inline void update(int i,ll k);
inline ll GetSum1(int i);
inline ll GetSum2(int i);
int main(){
char ch;
int a,b,c;
scanf ("%d %d",&N,&Q);
for (int i=1;i<=N;i++){
scanf ("%lld",&a1[i]); D[i] = a1[i] - a1[i-1];
update(i,D[i]);
}
while (Q--){
cin >> ch;
if (ch=='C'){
scanf ("%d %d %d",&a,&b,&c);
D[a] += c,D[b+1] -= c;
update(a,c);
update(b+1,-c);
continue;
}
scanf ("%d %d",&a,&b);
printf ("%lld\n",GetSum1(b)*b-GetSum2(b)-GetSum1(a-1)*(a-1)+GetSum2(a-1));
}
return 0;
}
ll GetSum2(int i){
ll ans = 0;
while (i){
ans += c2[i];
i -= lowbit(i);
}
return ans;
}
ll GetSum1(int i){
ll ans = 0;
while (i){
ans += c1[i];
i -= lowbit(i);
}
return ans;
}
void update(int i,ll k){
ll temp = k*(i-1);
while (i<=N){
c1[i] += k;
c2[i] += temp;
i += lowbit(i);
}
return;
}
0 条评论