题解 | 【模板】静态区间和（前缀和）

谁说前缀和不是dp(手动滑稽)

我们发现前i个数的和pre[i]就等于前i-1个数的和pre[i-1]加上第i个数a[i]

状态设计为pre[i]，表示前i个数的前缀和

转移方程为pre[i] = pre[i-1]+a[i]

再考虑查询，我们发现要统计[l,r]区间内的数字之和，如果取pre[r]就多算了前l-1个数之和，而前l-1个数之和恰好就是pre[l-1]，故查询的结果是pre[r]-pre[l-1]

实现：

C++可以用std::partial_sum计算前缀和，该函数在<numeric>头文件中，C++20开始支持

正好最近也在学习Python，贴一份C++代码，再贴一份Python代码

#include <iostream>
#include <vector>
#include <numeric>

using i64 = long long;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int n,q;
  std::cin >> n >> q;

  std::vector<i64> a(n+1);
  for(int i = 1; i <= n; i++){
    std::cin >> a[i];
  }

  std::vector<i64> pre(n+1);
  std::partial_sum(a.begin(),a.end(),pre.begin());

  auto query = [&](int l,int r){
    return pre[r]-pre[l-1];
  };

  for(int i = 0; i < q; i++){
    int l,r;
    std::cin >> l >> r;

    std::cout << query(l,r) << "\n";
  }
}

import sys

input = lambda: sys.stdin.readline().strip()

n,q = map(int,input().split())

a = list(map(int,input().split()))
a = [0]+a

pre = [0]*(n+1)
for i in range(1,n+1):
  pre[i] = pre[i-1]+a[i]

res = []
for i in range(q):
  l,r = map(int,input().split())
  res.append(pre[r]-pre[l-1])

print("\n".join(map(str,res)))