前缀和

发布于 2018-12-22  524 次阅读

前缀和是一种重要的思想

前言

好吧，本文用它来处理区间，先说说它的复杂度，它可以在O(n)的预处理后实现O(1)的区间查询，而线段树的时间复杂度为O(logN)。

一道水题。。。

要求

给你n个数和m次查询，每次查询要求你输出1～x的和。

输出输入格式

输入

第一行 n，m

第二行n个数a[]

接下来m行每行输入一个x代表1～x

输出

对于每次查询，输出1～x的每个数的和

输入：

5 2
1 3 5 2 4
3
4

输出：

9
11

解法

大家展开了一场激烈的讨论。

  • lz： 一个一个加

  • MoveToEx： 线段树 ！

  • 太阳 : 这不前缀和板子题么

我们开一个数组sum[]

接下来O(n)预处理

令sum[i] += a[i] + sum[i-1]

于是 两个数组对应如下

数组 column1 column2 column3 column4 column5
a 1 3 5 2 4
sum 1 4 9 11 15

发现，sum[i]存储了a[1～i]元素的和。

接下来O(1)输出就行了。

升级版

如果我们查询a[x～y]的和呢。

如果您问小学生，他们会毫不犹豫地回答：

“拿sum[y]-sum[x-1]就可以了~~~,这不小学数学减法题吗！？？”

...被小学生吊打

核心代码

void setup()
{
    for(int i-1;i<=n;i++)
        sum[i] = sum[i-1] + a[i];
}

int query(int l, int r) //查询
{
    return sum(r) - sum(l-1);
}

后记

有人问了，那修改怎么办呢，下一篇博文我会江的。。

"差分“