树状数组--前n项和；
浏览数：100 /
时间：2015年06月08日
树状数组是和线段树类似的数据结构，基本上树状数组可以做的线段树都可以做；
树状数组就是一个数组，在信息记录上有一些特点，以动态求前n项和为例：可以改变数组的某一个元素，求前n项和；
数组tree[ i ]记录的是A[ i - lowbit ( i )+1]~A[ i ]的和，lowbit（i），表示i的最低二进制是多少；表现在数组编号上就是上面的图中表现的东西；
求前n项和的操作：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 #define MAX 1000 5 inline int lowbit(int x) 6 { 7 return x&(-x); 8 } 9 int main() 10 { 11 int tree[MAX+10],a[MAX]; 12 for(int i=1;i<=MAX;i++)//编号从1开始； 13 scanf("%d",&a[i]); 14 //求前n项和的操作； 15 int n,ans=0; 16 scanf("%d",&n); 17 for(int i=n;i>0;i-=lowbit(i)) 18 { 19 ans+=tree[i]; 20 } 21 //给第n项数加m； 22 int m; 23 scanf("%d%d",&n,&m); 24 for(int i=1;i<=MAX;i+=lowbit(i)) 25 { 26 tree[i]+=m; 27 } 28 return 0; 29 }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
