There are two types of problems solvable by partial sum.
1.Problems which you are asked to answer some queries about the sum of a part of elements (without modify queries).
Solution of all of this problems are the same. You just need to know how to solve one of them.
Example : You are asked some queries on an array _a_1, _a_2, …a, n. Each query give you numbers l and r and you should print a__l + a__l + 1 + … + a__r .
Solution : You need to build another array _s_1, _s_2, …, s__n which s__i = _a_1 + _a_2 + … + a__i and answer is s__r - s__l - 1 .
2.Problems which you are asked to perform some queries asking you to modify a part of elements (without printing queries.)
Solution of all of this problems are the same. You just need to know how to solve one of them.
Example : You need to perform some queries on an array _a_1, _a_2, …a, n. Each query give you numbers l, r and v and for each i such that l ≤ i ≤ r you should increase a__i by v, and then after performing all queries, you should print the whole array.
Solution : You should have another array _p_1, _p_2, …, p__n which, all of its members are initially 0, for each query, you should increase p__l by v and decrease p__r + 1 by v .
An then, for each i, starting from 1 you should increase p__i by p__i - 1. So, final array would be _a_1 + _p_1, _a_2 + _p_2, …, a__n + p__n .
先说最简单也是最常见的一种。#
sum[i]=sum[i-1]+a[i] （初始sum[0]=0,所以a[i]的下标最好从1开始） 询问得到[l,r]的和，答案为sum[r]-sum[l-1];