一维前缀和

一维前缀和是指某序列的前n项和，相当于数学上的数列的前n项和。
时间复杂度分析：预处理前缀和数组O(n)；每次查询O(1)

为什么需要一维前缀和算法

求 [l, r] 区间内数组a的和：暴力做法需要遍历a [l, r]部分，时间复杂度为O(n)
而使用前缀和算法：对于每次查询，只需执行sum[r] - sum[l - 1] ，时间复杂度为O(1)
也就是说计算的时间从O(n)降为了O(1)。
因此当有多次查询时时，使用前缀和算法就可以大大节省时间。

如何计算一维前缀和数组

方法一：借助性质：

求出数组a的前缀和

def get_pre_sum(a):
    n = len(a)
    pre_sum = [0] * (n + 1)   # 初始化前缀和数组，+1可以避免处理l=0的边界情况
    for i in range(1, n + 1):
        pre_sum[i] = pre_sum[i - 1] + a[i - 1]
    return pre_sum

• 1
• 2
• 3
• 4
• 5
• 6
• 7

方法二：

from itertools import accumulate


def get_pre_sum(a):
    pre_sum = [0] + list(accumulate(a))  # 可以避免处理l=0的边界情况
    return pre_sum

• 1
• 2
• 3
• 4
• 5
• 6

tips：方法二实现速度更快哦

如何实现区间求和

# 计算区间[l, r]的和
def get_sum(pre_sum, l, r):
    return pre_sum[r + 1] - pre_sum[l] 
    # 前缀和数组的索引从1开始(0是初始值)，所以r+1
    # 这样可以避免处理l=0的边界情况

• 1
• 2
• 3
• 4
• 5

实战演练1： 区间次方和

点此进入题目页面https://www.lanqiao.cn/problems/3382/learning/?page=1&first_category_id=1&problem_id=3382

一开始的想法：

n, m = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
for _ in range(m):
    l, r, k = map(int, input().split())
    temp_a = [x ** k for x in a]
    print(get_sum(get_pre_sum(temp_a), l - 1, r - 1) % mod)

• 1
• 2
• 3
• 4
• 5
• 6
• 7

发现超时，仔细一想：查询次数m时1e5，如果每次在查询中计算数组的k次方必然会超时。再读一下题目的数据范围k是在1到5，不妨将数组的1到5次方都计算出来后放置于一个列表pre_sum_list 中，每次查询使用pre_sum_list [k-1]即可。

题解：

mod = 10 ** 9 + 7
def get_pre_sum(a):
    pre_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        pre_sum[i] = pre_sum[i - 1] + a[i - 1]
        pre_sum[i] %= mod
    return pre_sum


def get_sum(pre_sum, l, r):
    return (pre_sum[r + 1] - pre_sum[l]) % mod


n, m = map(int, input().split())
a = list(map(int, input().split()))
pre_sum_list=[]
for i in range(1,6):
    temp_a = [x ** i for x in a]
    pre_sum_list.append(get_pre_sum(temp_a))
for _ in range(m):
    l, r, k = map(int, input().split())
    print(get_sum(pre_sum_list[k-1], l - 1, r - 1) % mod)

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23

别忘了在求前缀和数组、区间和时对mod进行模运算。

实战演练2：小郑的蓝桥平衡串

点此进入题目页面https://www.lanqiao.cn/problems/3419/learning/?page=1&first_category_id=1&problem_id=3419

思路分析：

找最长连续特定子串问题：一开始想到使用滑动窗口技术，随后发现不满足单调性，无法使用双指针维护窗口。
仔细审题发现需要保证两个字符 L,Q数量必须相等，不妨将L,Q变为1，-1，并存入数组中。
接着遍历数组前缀和，找到最大的和为0的区间即为答案。

题解：

def get_pre_sum(a):
    pre_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        pre_sum[i] = pre_sum[i - 1] + a[i - 1]
    return pre_sum


def get_sum(pre_sum, l, r):
    return pre_sum[r + 1] - pre_sum[l]


s = input()
n = len(s)
a = [0] * n
ans = 0
for i in range(n):
    if s[i] == 'L':
        a[i] = 1
    else:
        a[i] = -1
for l in range(n):
    for r in range(l, n):
        if get_sum(get_pre_sum(a), l, r) == 0:
            ans = max(ans, r - l + 1)
print(ans)

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26

讲到前缀和，就得关联差分，它们互为逆运算，点此进入差分的学习吧！http://iyenn.com/rec/1618848.html?spm=1001.2014.3001.5501