小工具知识网

当前位置: 首页 > 行业知识 > 根号分治(根号算法)

行业知识

根号分治(根号算法)

2026-11-19 23:05:09 来源:互联网转载

���根号算法,然而不是分块;

()

是论文,然而不是莫队;

是暴力美学,然而不是暴力。

()

例题

  • 哈希冲突
  • R e m a i n d e r P r o b l e m Remainder Problem RemainderProblem

    这两题貌似没有区别,我们以 R e m a i n d e r P r o b l e m Remainder Problem RemainderProblem 作为例子来介绍。

    题目描述

    给你一个长度为 500000 500000 500000 的序列,初值为 0 0 0 ,你要完成 q q q 次操作,操作有如下两种:

    1. 1 x y : 将下标为 x x x 的位置的值加上 y y y
    2. 2 x y : 询问所有下标模 x x x 的结果为 y y y 的位置的值之和

    思路

    这道题要我们求的,就是以下程序:

    for(int i=y;i                                   n                                       x > \sqrt{n}                  x>n            ​ 时,就暴力求解;                                    x                         ≤                                   n                                       x \le \sqrt{n}                  x≤n            ​ 时,则预处理出答案。 

    如此,当数据 ≤ n \le \sqrt{n} ≤n ​ 时,每次修改的时间复杂度为为 O ( n ) O(\sqrt{n}) O(n ​) ,查询的为 O ( 1 ) O(1) O(1) ;

    当数据 > n > \sqrt{n} >n ​ 时,每次修改的时间复杂度为 O ( 1 ) O(1) O(1) ,查询的为 O ( n ) O(\sqrt{n}) O(n ​) 。

    通过根号分治,我们就能实现两种操作的时间复杂度均分 。

    对于预处理,我们用 f i , j f_{i,j} fi,j​ 表示所有下标模 i i i 为 j j j 的数的和。

    f f f 数组只需开到 n ∗ n \sqrt{n} * \sqrt{n} n ​∗n ​ ,所以空间也不会爆。

    代码

    #includeusing namespace std;const int maxn=5e5+5,N=5e5,sqrtn=710;int q;long long a[maxn],f[sqrtn][sqrtn];int main(){cin>>q;int opt,x,y,tmp=sqrt(N);while(q--){scanf("%d%d%d",&opt,&x,&y);if(opt==1){ //修改操作 for(int i=1;i //查询操作 if(xlong long ans=0;for(int i=y;i

上一篇:深度解析,字长概念、定义、作用及其重要性!

下一篇:网页视频下载秘籍,轻松掌握视频下载技巧!