浅谈分块

区间修改,单点查询

• 众所周知，这种题线段树是可以跑得下来的，但是线段树的常数太大了，前几天本蒟蒻改一道线段树题改到自闭，调好之后就被卡掉了，太可怕了。蒟蒻就手残，打了一篇博客......

分块大法

• 对于任意一个序列{a}，给定两种操作:

  0:给定l,r,c把l-r中a[i] (l=<i<=r)的值都加上c；

  1:给定l,r,c(l,c可以忽略)查询a[r]的值。

• 虽然线段树数据结构是O(nlogn),分块是O(n sqrt(n))的复杂度。但是分块可以维护好多东西.

分块的实现

• 分块就是把一个区间分成好几个小块，大部分题的复杂度都是n sqrt(n)，所以默认是把区间分成sqrt(n)块。如果某题用分块复杂度带log，就让块分的更多一些，大概是乘个log。

维护

• 当询问某段区间时，把区间覆盖的整块打上一个num标记，两边离散的块呢，就暴力就好了。最后输出时把num加上。询问区间如果在一个块里要特判，所以要多打几个if。

不废话了,请看代码

#include
      
       #define ll long longusing namespace std;ll n,k;struct block{    ll val;//数值    ll idd;//第几块}a[50010];ll num[50010];inline void add(int l,int r,int c){      if(a[r].idd-a[l].idd<2)      {          for(int i=l;i<=r;i++)              a[i].val+=c;          return ;      }      for(int i=a[l].idd+1;i