RainAir
My OI Blog
RainAir

树状数组
文章归档

二维树状数组学习笔记

我们把树状数组由一维扩展到二维。二维树状数组的定义是: $C[x][y] = \sum A[i][j]$,其中 $x - lowbit(x) + 1 \leq i \leq x$ $y - lowbit(y) + 1 \leq j \leq y$ 所以我们就可以很方便的写出来单点修改和查询 $(1,1)$ 到 $(x,y)$ 的和的代码了: [crayon-5dd7d48e…

   442   2019-02-07   442 去吊打作者

「SHOI2007」园丁的烦恼

题目描述 题目链接 平面上有 $n$ 个点 $(x_i, y_i)$,$m$ 次询问,每次询问为一个矩形内有多少点。 允许离线。 其中 $ n,m \leq 500000 $。 解题报告 首先这个东西显然可以二维前缀和来预处理。 具体来说就是设这个前缀和数组为 $S$,每次暴力预处理,暴力查询…

   364   2018-10-01   364 去吊打作者
标签
近期评论