1104 Sum of Number Segments（20 分）
Given a sequence of positive numbers, a segment is defined to be a consecutive subsequence. For example, given the sequence { 0.1, 0.2, 0.3, 0.4 }, we have 10 segments: (0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4) (0.3) (0.3, 0.4) and (0.4).
Now given a sequence, you are supposed to find the sum of all the numbers in all the segments. For the previous example, the sum of all the 10 segments is 0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9 + 0.3 + 0.7 + 0.4 = 5.0.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N, the size of the sequence which is no more than 105. The next line contains N positive numbers in the sequence, each no more than 1.0, separated by a space.
Output Specification:
For each test case, print in one line the sum of all the numbers in all the segments, accurate up to 2 decimal places.
Sample Input:
4
0.1 0.2 0.3 0.4
Sample Output:
5.00题目大意：给出一个序列，找出所有的子序列，并对子序列求和输出。
//首先就想到用树状数组，所以写了一个树状数组巩固一下，其中遇到了一些小问题，解决之后提交pat发现运行超时，只通过了两个测试点，应该是不能用这个来做了。
#include <iostream>
#include <stdio.h>
using namespace std;
float a[];
int lowbit(int x){
return x&-x;
} void update(int index,float x){//为什么你会死循环呢？
//因为！！树状数组下标应该从1开始的！！！
for(int i=index;i<=;i+=lowbit(i)){
a[i]+=x;
}
} float getsum(int x){
float ret=0.0;
for(int i=x;i>;i-=lowbit(i)){
ret+=a[i];
}
return ret;
} int main() {
int n;
scanf("%d",&n);
float x;
for(int i=;i<=n;i++){
scanf("%f",&x);
update(i,x);
}
// for(int i=1;i<=4;i++)
// printf("%f ",a[i]);
float sum=0.0;
for(int i=;i<=n;i++){
for(int j=i;j<=n;j++){
if(i==){
sum+=getsum(j);
}else {
sum+=(getsum(j)-getsum(i-));
} }
}
printf("%.2f",sum);
return ;
}
//基本上是O（n^2）的复杂度。
小问题：1.getsum函数没有对ret进行返回。。。导致sum一直输出nan....
2.树状数组下标应该从1开始！不是0，0会导致update死循环。
代码来自：https://www.liuchuo.net/archives/1921
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
double a[];
double sum = 0.0;
for (int i = ; i <= n; i++) {
cin >> a[i];
sum = sum + a[i] * i * (n - i + );//这里计算每个数出现的次数！。
//是一个找规律的问题。
}
printf("%.2f", sum);
return ;
}
//当我看到这个题的代码如此短小精悍，惊呆了。
//还是有点不明白，搜索了一下：
对于第i个数字(i=0~n-1)，它每组出现的次数为n-i，出现在前i+1个组中
非常厉害！学习了！