#include using namespace std; const int N = 1e5 + 10; int n, a[N]; //下面是用树状数组完成前缀和的保存办法 #define lowbit(x) (x & -x) int c[N]; //点更新 void add(int i, int z) { for (; i <= n; i += lowbit(i)) c[i] += z; //更新所有祖先 } //前缀和 int sum(int i) { int s = 0; for (; i; i = i - lowbit(i)) s += c[i]; return s; } //区间和 int sum(int i, int j) { return sum(j) - sum(i - 1); } /* 测试用例: 5 2 3 1 4 5 */ int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); add(i, a[i]); } //利用树状数组求前缀和 printf("%d\n", sum(4)); //利用树状数组求区间和 printf("%d\n", sum(5) - sum(3)); return 0; }