10.25 01字典树 and 分块

· · 算法·理论

01字典树

先用一个题目举个例子：PP10471 最大异或对 The XOR Largest Pair

题意：

在n个数中任意选择两个数，最大异或和为多少？

思路：

  2. 用01字典树

    首先注意到异或运算是相同为0，不同为1，所以我们需尽可能让更多的位数不同，那怎么让其尽可能多的不同呢？

    首先，我们可以将每个数转化为二进制存入字典树中：

    对于每个新加入的数从第一位开始向后枚举，使每一位仅可能走岔路，即尽可能选与当前位不同的数值，使其异或值最大

注意到每个数需要在前面补齐0，这样只要开头越先出现1则一定更优

掏个代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N(1e5+10);
int n,ans(0),tot(0);
int a[N],tr[N*32][2];
void cr(int v){
    int u(0);
    for(int k(30);k>=0;k--){
        int c((v>>k)&1);
        if(!tr[u][c]) tr[u][c]=++tot;
        u=tr[u][c];
    }
    return;
}
int qry(int v){
    int u(0),sum(0);
    for(int k(30);k>=0;k--){
        int c((v>>k)&1);
        if(tr[u][c^1]) u=tr[u][c^1]; sum+=(1<<k);
        else u=tr[u][c];
    }
    return sum;
}
int main(){
    cin>>n;
    for(int i(1);i<=n;i++){
        cin>>a[i];cr(a[i]);
        ans=max(ans,qry(a[i]));
    }
    cout<<ans<<'\n';
    return 0;
}

分块

分块的基本思想是，通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。

分块的时间复杂度主要取决于分块的块长，一般可以通过均值不等式求出某个问题下的最优块长，以及相应的时间复杂度。

区间和

我们将序列按每s个元素一块进行分块，并记录每块的区间和b_i

a_1,a_2,...,a_s\\b_1\\ a_{s+1},...,a_{2s}\\ b_2\\ a_{(s-1)\times s+1},...,a_n\\ b_{\frac{n}{s}}

注意到s不能每次都整除n，but 对操作影响不大

首先看查询操作：

而对于修改则与查询相同：

对于不完整的块，仍然是暴力修改每个元素的值并更新 b_i，对于完整块，则直接修改 b_i 即可