树状数组--前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 }

 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 编程语言 Java C C# Javascript js Python Ruby Spring 程序 VB

相关文章

随机文章

您可能还喜欢

您可能还喜欢