给你n个数。请你求这n个数的和。

算法1：暴力求和

直接用一个循环遍历这n个数，将它们累加起来即可。

时间复杂度：$O(n)$

C++ 代码

#include <iostream>
using namespace std;

int main() {
    int n, sum = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sum += x;
    }
    cout << sum << endl;
    return 0;
}

算法2：快速求和

这个算法利用了等差数列的求和公式，即$1+2+3+\cdots+n=(1+n)n/2$。

时间复杂度：$O(1)$

C++ 代码

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int sum = (1 + n) * n / 2;
    cout << sum << endl;
    return 0;
}

算法3：递归求和

递归求和的思路是不断将n个数拆分成两个部分，分别求它们的和，然后将这两个和相加。

时间复杂度：$O(n\log n)$

C++ 代码

#include <iostream>
using namespace std;

int sum(int a[], int l, int r) {
    if (l == r) return a[l];
    int mid = (l + r) / 2;
    return sum(a, l, mid) + sum(a, mid+1, r);
}

int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cout << sum(a, 0, n-1) << endl;
    return 0;
}