前缀和

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


前缀和是一种重要的思想

前言

好吧,本文用它来处理区间,先说说它的复杂度,它可以在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);
}

后记

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

"差分“