标签: 前缀和

1 篇文章

专题——高维前缀和
前缀和 想必大家都已经很清楚前缀和的作用了。 前缀和是一种重要的预处理,能大大降低查询的时间复杂度。可以简单理解为“数列的前 $n$ 项的和”。 它可以将区间查询求和从 $O(n)$ 降至 $O(1)$。 高维前缀和 所谓“高维前缀和”,就是指”二维及以上“的前缀和 例如我们给定一个矩阵: 1 2 4 3 5 1 2 4 6 3 5 9 那么它的前…