标题指的是这类问题：
我们经常会看见求 \(\sum\limits_{x=l}^r\sum\limits_{y=x}^r f(x,y)\) 这类问题。我们常常能够通过智慧将 \(f(x,y)\) 转化为二维平面上的点，然后发现所有 \(f\) 可以用一些矩形加来表示。通常这里面矩形加的次数是 \(\mathcal O(n)\) 或者 \(\mathcal O(n\log n)\) 等低复杂度的。那么得到这些矩形后应该怎么做呢？
方法 \(\mathit1\) - 线段树历史版本和
将其中一维扫描线，将修改和查询都拆成两部分，然后就是线段树历史版本和了。
时间复杂度 \(\mathcal O((m+q)\log n)\)，其中 \(n\) 是原序列大小，\(m\) 是修改次数，\(q\) 是查询次数。
方法 \(\mathit2\) - 树状数组
可以将修改拆成 \(4\) 个后缀矩形加，将查询拆成 \(4\) 个前缀矩形查，那么发现这样一来有贡献的修改操作就是端点再前缀矩形内的。那么还是一维扫描线，另一维用树状数组维护。
具体地，一个修改操作 \((x,y,v)\) 对一个查询操作 \((a,b)\) 的贡献是：
\[v(a-x+1)(b-y+1)={\color{red}v}(a+1)(b+1)-{\color{red}vx}(b+1)-{\color{red}vy}(a+1)+{\color{red}vxy} \]将四个红色部分分别维护就行了。时间复杂度仍是 \(\mathcal O((m+q)\log n)\) 的。
以上两种方法复杂度相同，但是哪个的常数更优秀呢？实践证明，树状数组虽然要拆成 \(4\) 个操作，每个操作又要维护 \(4\) 个部分，保底就有 \(16\) 的常数了，但是树状数组常数本身较小，而线段树涉及标记下传等，还有递归操作，所以实际上树状数组的常数是要略胜一筹的。
方法 \(\mathit3\) - 四分树
我只是提一嘴。
标签：拆成,树状,复杂度,red,经典,mathcal,矩形,解法,若干 From： https://www.cnblogs.com/tulipenoire/p/18017796