首页 > 代码库 > 树状数组
树状数组
给定一个区间，如果要频繁修改该区间内的元素，且频繁查询该区间内任意小区间的元素之和时，可以用树状数组。
普通的一次修改时间复杂度是O(1)，而查询的时间复杂度是O(n). 树状数组的修改和查询的时间复杂度均为O(logn)
给定区间1-->n，区间内对应的元素为a[i] (1 <= i <= n )
树状数组是这样一个数组c
c[i] = a[i - 2^k + 1] + ... + a[i] , k 为i在二进制下末尾0的个数（所以树状数组不能从0开始，只能从1开始)，也即2^k是i在二进制下，第一个不为0的bit所表示的大小
1 int lowbit(int t)2 {3 return t&(-t);4 }
lowbit(t); 的作用是求出t在二进制下，第一个不为0的bit所表示的大小
4(10) = 0000 0100(2) lowbit(4) = 4;
-4(10) = 1111 1100(2) 4&(-4) = 0000 0100
5(10) = 0000 0101(2) lowbit(5) = 1
-5(10) = 1111 1011(2) 5&(-5) = 0000 0001
如果，当要修改一个元素a[pos]时，就要修改c[pos]及其c[pos]的父亲，c[pos]父亲的父亲，即c[pos]往根结点一路上溯，不断修改c[]即可
c[pos]的父结点的下标为 pos += lowbit(pos)
1 void modify(int pos, int val)//当a[pos]发生改变时2 {3 while(pos <= n)4 {5 c[pos] += val;//c[pos] 肯定包含a[pos] ,但是之后的c数组，哪个又包含a[pos]呢6 pos += lowbit(pos);//c[pos]的父结点的下标为 pos += lowbit(pos)7 }8 }
如图，如果求前n项的和，比如n=6时，c[6] = a[5] + a[6],c[6]包含lowbit(6)项，即2项，所以还要求得前4项的和，即n-=lowbit(n)
1 int getSum(int pos) 2 { 3 int sum = 0; 4 while(pos >= 1) 5 { 6 sum += c[pos]; 7 pos -= lowbit(pos); 8 } 9 return sum;10 }
hdu1166敌兵布阵 http://acm.hdu.edu.cn/showproblem.php?pid=1166
1 #include <stdio.h> 2 #include <string.h> 3 const int N = 50000 + 10; 4 int c[N], n; 5 int lowbit(int t) 6 { 7 return t&(-t); 8 } 9 void modify(int pos, int val)//当a[pos]发生改变时10 {11 while(pos <= n)12 {13 c[pos] += val;//c[pos] 肯定包含a[pos] ,但是之后的c数组，哪个又包含a[pos]呢14 pos += lowbit(pos);//c[pos]的父结点的下标为 pos += lowbit(pos)15 }16 }17 int getSum(int pos)18 {19 int sum = 0;20 while(pos >= 1)21 {22 sum += c[pos];23 pos -= lowbit(pos);24 }25 return sum;26 }27 int main()28 {29 int t, val, a, b, i, tCase = 1;30 char op[10];31 scanf("%d",&t);32 while(t--)33 {34 memset(c, 0, sizeof(c));35 scanf("%d",&n);36 for(i=1; i<=n; ++i)37 {38 scanf("%d",&val);39 modify(i, val);40 }41 printf("Case %d:\n",tCase++);42 while(true)43 {44 scanf("%s",op);45 if(op[0] == ‘E‘)46 break;47 if(op[0] == ‘Q‘)48 {49 scanf("%d%d",&a,&b);50 int ans = getSum(b);51 if(a - 1 >= 1)52 ans -= getSum(a-1);53 printf("%d\n",ans);54 }55 else if(op[0] == ‘A‘)56 {57 scanf("%d%d",&a,&b);58 modify(a, b);59 }60 else61 {62 scanf("%d%d",&a,&b);63 modify(a, -b);64 }65 }66 67 }68 return 0;69 }
扩展---二维树状数组
一维树状数组很容易扩展到二维，二维树状数组如下所示：
C[x][y] = sum(A[i][j])
其中，x-lowbit[x]+1 <= i<=x且y-lowbit[y]+1 <= j <=y
http://acm.fafu.edu.cn/problem.php?id=1100
一个由数字构成的大矩阵，能进行两种操作
1) 对矩阵里的某个数加上一个整数（可正可负）
2) 查询某个子矩阵里所有数字的和
要求对每次查询，输出结果
树状数组解法：
1 #include <stdio.h> 2 #include <string.h> 3 const int N = 1024 + 10; 4 int c[N][N], n; 5 void init() 6 { 7 for(int i=0; i<=n; ++i) 8 for(int j=0; j<=n; ++j) 9 c[i][j] = 0;10 }11 int lowbit(int t)12 {13 return t & (-t);14 }15 void modify(int x, int y, int val)16 {17 for(int i=x; i<=n; i+=lowbit(i))18 for(int j=y; j<=n; j+=lowbit(j))19 c[i][j] += val;20 }21 int getSum(int x, int y)22 {23 int ans = 0;24 for(int i=x; i>=1; i-=lowbit(i))25 for(int j=y; j>=1; j-=lowbit(j))26 ans += c[i][j];27 return ans;28 }29 int main()30 {31 int op,x, y, a, l, b, r, t;32 while(scanf("%d%d",&x,&n)!=EOF)33 {34 init();35 while(scanf("%d",&op) && op != 3)36 {37 switch(op)38 {39 case 1:40 scanf("%d%d%d",&x,&y,&a);41 ++x; ++y;42 modify(x, y, a);43 break;44 case 2:45 scanf("%d%d%d%d",&l,&b,&r,&t);46 ++l; ++b; ++r; ++t;47 printf("%d\n",getSum(r,t) + getSum(l-1,b-1) - getSum( r,b-1 )-getSum(l-1,t) ); 48 break;49 }50 }51 }52 return 0;53 }
线段树解法:
1 /* 2 0 4 3 1 1 2 3 4 2 0 0 2 2 5 1 1 1 2 6 1 1 2 -1 7 2 1 1 2 3 8 3 9 多重二分--->线段树的每个结点也是一颗树 10 将x二分，每次将x二分的情况下再将y二分 11 */ 12 //#define _CRT_SECURE_NO_DEPRECATE 13 #include <iostream> 14 #include <string.h> 15 #include <stdio.h> 16 using namespace std; 17 typedef __int64 LL; 18 const int N = 1024 + 10; 19 int sum[N * 3][N * 3]; 20 int n,op, x, y, v, L,B,R,T; 21 LL ans; 22 void sub_update(int f, int sLoc, int val, int l, int r, int rt) 23 { 24 if(l == r) 25 { 26 sum[f][rt] += val; 27 return; 28 } 29 int mid = (l + r) >> 1; 30 if(sLoc <= mid) 31 sub_update(f, sLoc, val, l, mid, rt<<1); 32 else 33 sub_update(f, sLoc, val, mid+1, r, rt<<1|1); 34 sum[f][rt] = sum[f][rt<<1] + sum[f][rt<<1|1]; 35 } 36 void update(int fLoc, int sLoc, int val, int l, int r, int rt) 37 { 38 sub_update(rt, sLoc, val, 1, n, 1); 39 if(l == r) 40 return; 41 int mid = (l + r) >> 1; 42 if(fLoc <= mid) 43 update(fLoc, sLoc, val, l ,mid, rt<<1); 44 else 45 update(fLoc, sLoc, val, mid+1, r, rt<<1|1); 46 } 47 48 LL sub_query(int f, int sL, int sR, int l, int r, int rt) 49 { 50 if(sL == l && sR == r) 51 return sum[f][rt]; 52 int mid = (l + r) >> 1; 53 LL ret = 0; 54 if(sR <= mid) 55 ret += sub_query(f, sL, sR, l, mid, rt<<1); 56 else if(sL > mid) 57 ret += sub_query(f, sL, sR, mid+1, r, rt<<1|1); 58 else 59 { 60 ret += sub_query(f, sL, mid, l, mid, rt<<1); 61 ret += sub_query(f, mid+1, sR, mid+1, r, rt<<1|1); 62 } 63 return ret; 64 } 65 LL query(int fL, int fR, int sL, int sR, int l, int r, int rt) 66 { 67 if(fL == l && fR == r) 68 return sub_query(rt, sL, sR, 1, n, 1); 69 int mid = (l + r) >> 1; 70 LL ret = 0; 71 if(fR <= mid) 72 ret += query(fL, fR, sL, sR, l, mid, rt<<1); 73 else if(fL > mid) 74 ret += query(fL, fR, sL, sR, mid+1, r, rt<<1|1); 75 else 76 { 77 ret += query(fL, mid, sL, sR, l, mid, rt<<1); 78 ret += query(mid+1, fR, sL, sR, mid+1, r, rt<<1|1); 79 } 80 return ret; 81 } 82 void input(int &x) 83 { 84 char ch = getchar(); 85 bool flag = ch == ‘-‘; 86 while(ch<‘0‘ || ch>‘9‘) 87 { 88 ch = getchar(); 89 if(ch == ‘-‘) 90 flag = true; 91 } 92 x = 0; 93 while(ch>=‘0‘ && ch<=‘9‘) 94 { 95 x = x * 10 + ch -‘0‘; 96 ch = getchar(); 97 } 98 x = flag ? -x : x; 99 }100 int main()101 {102 while(scanf("%d%d",&op,&n)!=EOF)103 {104 ++n;105 memset(sum, 0, sizeof(sum));106 while(true)107 {108 //scanf("%d",&op);109 input(op);110 if(op == 1)111 {112 //scanf("%d%d%d",&x,&y,&v);113 input(x);input(y);input(v);114 ++x; ++y;115 update(x, y, v, 1, n, 1);116 }117 else if(op == 2)118 {119 input(L);input(B);input(R);input(T);120 //scanf("%d%d%d%d",&L,&B,&R,&T);121 ++L; ++B; ++R; ++T;122 printf("%I64d\n",query(L, R, B, T, 1, n, 1));123 }124 else125 break;126 }127 }128 }
二维线段树入门：http://wenku.baidu.com/view/bdc5eb0216fc700aba68fc05.html
树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。