111qqz的小窝

老年咸鱼冲锋!

前缀和问题总结

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 a1, a2, …a, n. Each query give you numbers l and r and you should print al + al + 1 + … + ar .

Solution : You need to build another array s1, s2, …, sn which si = a1 + a2 + … + ai and answer is sr - sl - 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 a1, a2, …a, n. Each query give you numbers l, r and v and for each i such that l ≤ i ≤ r you should increase ai by v, and then after performing all queries, you should print the whole array.

Solution : You should have another array p1, p2, …, pn which, all of its members are initially 0, for each query, you should increase pl by v and decrease pr + 1 by v .

An then, for each i, starting from 1 you should increase pi by pi - 1. So, final array would be a1 + p1, a2 + p2, …, an + pn .

 

先说最简单也是最常见的一种。
sum[i]=sum[i-1]+a[i] (初始sum[0]=0,所以a[i]的下标最好从1开始)
询问得到[l,r]的和,答案为sum[r]-sum[l-1];

还有一种遇到相对较少的用法。 每次对数组a的某区间[l,r]内的每个数增加x。最后要求输出经过所有变换后的数组a。做法是:声明另一个数组p,当对区间[l,r]增加x时, p[l]+=x,p[r-1]-=x; 所有的变换完成后,另p[i]+=p[i-1] ,那么最后的答案就是p[i]+a[i](i:1..n) (可以这样理解:p[l]+=x,表示从x开始被增加x这个变换影响,一直影响到r,也就是从r+1取消这种变换的效果,所以p[r+1]-=x,然后处理前缀和,把标记在开头的变幻累计到每个元素)

此外:前缀和不一定是“和”,加法可以推广到任何有“前缀和性质”的运算,比如乘积,异或(虽然那样就应该不叫前缀“和”了2333)

  cf617E异或前缀和

这些都是区间上的前缀和,我们可以进一步推广到树上。区间的前缀和是从第一个节点开始累加,树上则是从根节点开始做dfs然后累加。

树上前缀和hdu5416

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz