分块算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了分块算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1379字，纯文字阅读大概需要2分钟。

内容图文

浅谈分块

区间修改,单点查询

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

分块大法

• 对于任意一个序列{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<bits/stdc++.h>
#define ll long long
using 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<a[r].idd;i++)//区间修改
          num[i]+=c;
      for(int i=l;i<=a[l].idd*k;i++)
          a[i].val+=c;
      for(int i=(a[r].idd-1)*k+1;i<=r;i++)
          a[i].val+=c;
      return ;
}
int main()
{
      scanf("%d",&n);
      k=sqrt(n);
      for(int i=1;i<=n;i++)
      {
          scanf("%d\n",&a[i].val);
          a[i].idd=(i-1)/k+1;
      }
      for(int i=1,opt,l,r,c;i<=n;i++)
      {
          scanf("%d%d%d%d",&opt,&l,&r,&c);
          if(!opt)add(l,r,c);
          else  printf("%d\n",a[r].val+num[a[r].idd]);
                  //单点查询
      }
}

Block Code

 

内容总结

以上是互联网集市为您收集整理的分块算法全部内容，希望文章能够帮你解决分块算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---