Question

C/C++如何快速地求出数组中连续的几个元素的和。

注意是快速的，一定是比较特殊的方法。本人初学者。

Answer 1

线段树或者树状数组可以求连续N个元素的和，每次求和时间复杂度O(log N).

追问

可以写出代码吗

追答

如果只是求和，用树状数组就不错，思想简单，实现也不复杂。代码倒是可以贴，不过树状数组的原理比较简单，建议稍微了解一下。

http://baike.baidu.com/link?url=Ct49EXZtdYCd50TBjt9gP-3rH4qhhErH-OPZ48V_eMh739ZtxQ0UYmbUBo9dXFqShChuSFTi3ipdP_E4qVLbj_
上边是百度百科，或者也可以自己搜树状数组随便看看。
int Lowbit(int t) //树状数组是根据数的二进制表示来存储数据的，这个函数用来计算某个数的二进制中的最低非0位，用了点小技巧
{
return t & ( t ^ ( t - 1 ) );
}
int Sum(int end) //求前end个元素的和，如果想求从第M个元素到第N个元素的和，就用Sum(N)-Sum(M-1)
{
int sum = 0;
while (end > 0)
{
sum += in[end];
end -= Lowbit(end);
}
return sum;
}
void plus(int pos , int num) //在第pos个元素上加上num，初始的数组赋值要用这个函数赋值。
{
while(pos <= n)
{
in[pos] += num;
pos += Lowbit(pos);
}
}

追问

帮到底吧，给个完全能运行的代码，

追答

那就给你用C++写了，
#include

using namespace std;

int n;
int in[1000000];

int Lowbit(int t)
{
return t & ( t ^ ( t - 1 ) );
}
int Sum(int end)
{
int sum = 0;
while (end > 0)
{
sum += in[end];
end -= Lowbit(end);
}
return sum;
}
void Plus(int pos , int num)
{
while (pos > n;//输入数据个数
for (int i=0;i> x;
Plus(i,x);
}
int l,r;
cin >> l >> r;//输入查询区间
cout << Sum(r)-Sum(l-1) << endl;
return 0;
}

Answer 2

这个还有什么特殊的。元素又没有规律