修改与在线询问如何加速？

KEY:让修改与在线询问的复杂度尽量平均
例

第一眼看 一头雾水
若每次修改暴力模拟,询问时直接输出点权,最坏:\(O(qm+1)\)//前者修改 后者询问
若每次修改在原地打lazy,询问时累加相邻的点及自己的点权,最坏:\(O(1+qm)\)//前者修改 后者询问
怎么办呢:折中
怎么办呢:分类
取\(k=\sqrt m\)(看完你会知道为什么取这个)

修改时(1 x y){
  先将自己val[x]+=y
  再遍历所有相邻的点(设为z){
    若该点z度数>=k，则val[z]+=y
    若该点z度数<k，则不变
  }
  tag[x]+=y//那不是少了度数<k的点的份？不然，加个tag
}
询问时(0 x){
  若该点x度数>=k，则直接输出val[x]
  若该点x度数<k，则输出val[x]+tag[S]//S为x相邻的度数>=k的点的集合
}

复杂度\(O(q\frac{m}{k}+qk)=O(q\sqrt m)\)
\(k=\sqrt m\)时\(\frac{m}{k}=k\)使其平均
这就是木桶原理:
水桶盛水量多少的关键因素不是其最长的板块，而是其最短的板块
程序总体时间复杂度大小的关键因素不是其最快的子程序，而是其最慢的子程序
ACcode
先鸽着

修改与在线询问如何加速？

原文：https://www.cnblogs.com/zhangshaojia/p/14994491.html