一维前缀和

前缀和 s[i]=a[1]+…+a[i]，则区间和 a[l..r]=s[r]-s[l-1]，O(1) 查询。预处理：for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];。适合数组不变、多次区间求和。