前缀和表长什么样
运行下面这段程序： def build_prefix(a): p = [] s = 0 for x in a: s += x p.append(s) return p pri
用它求中间三个数的和
同一张表，求下标 1 到 3 的和。运行下面这段程序： def build_prefix(a): p = [] s = 0 for x in a: s += x p.append(s)
把前缀和表建出来
补全 build_prefix：返回一个列表，第 i 项是前 i+1 个数的总和。 建好之后把整张表拼起来输出（用 / 隔开）。
用前缀和查区间和
补全 range_sum：用前缀和求下标 l 到 r 的和。 ⚠️ l 是 0 的时候不能去取 p[-1]。 求下标 1 到 3 的和。
换来的到底是多少
补全两个函数：brute_ops(n, m) 返回"每次都从头加一遍"做 m 次查询的操作数；prefix_ops(n, m) 返回"先建表再查"的操作数。 算 n=1000、m=1000 的情况，把
为什么小数据上 O(n²) 有时更快
数据量很小时，O(n²) 的做法有时反而比 O(n log n) 快，因为【0】。
判断"能撑多大数据"要看什么
判断一个算法能不能撑住更大的数据，看的是【0】。
数据量翻倍，O(n²) 会怎样
数据量翻一倍，一个 O(n²) 的算法耗时大约变成原来的【0】。
翻倍之后差了几倍
运行下面这段程序： def sq(n): return n * n print(sq(200) // sq(100))
大数据下两种做法差多少
一千个元素、一千次查询。运行下面这段程序： def brute_ops(n, m): return n * m def prefix_ops(n, m): return n + m print(brute_ops(100