算法学习:倍增思想

发布于 / 算法学习 / 0 条评论

个人认为来源于二进制的思想。

一系列区域

对于如图式的一系列区域。

以往的记录方式,都是从A出发,走一步到了A右面一格,走两步到了A右面两格位置,……,走11步,走到了B位置。这样记录的话,每个节点都需要记录 n – i 条内容,全部也就是需要 \frac{n(n-1)}{2}条,也就是 O(n^2) 的空间复杂度。而由于每个数都可以写为2进制,那么每个点我只需要记录走一步、走两步、走四步、走八步……的位置,比如从A点,我可以走 1+2+8=11 步到达B,也就是读取A走1步后在读取目前这个格子走两步再读取目前这个格子走八步的位置就可以到达B点。

而对于每一个点,走4步的位置就相当于走两步后的位置再走两步,走八步的位置就相当于走两步的位置再走两步再走两步……以此类推。

位运算符

位运算符为二进制运算符,所以是将参与运算的数据转换为二进制后进行运算。按右对齐,左补符号位运算。

  • >>:右移运算符,右移 i 位相当于将该数乘以了 2^i
  • <<:左移运算符,左移 i 位相当于将该数除以了 2^i
  • &:按位与运算,如 5 & 3 相当于即为(0101)_2 & (0011)_2 = (0001)_2,所以结果为1
  • |:按位或运算 ,如 5 | 3 相当于 (0101)_2 | (0011)_2 = (0111)_2,所以结果为7
  • ~:按位取反。
  • ^:异或运算符,如 5^3 相当于 (0101)_2 ^ (0011)_2 = (0110)_2,所以结果为6
    • 异或交换律:a\otimes b = b\otimes a
    • 异或结合律:(a\otimes b)\otimes c= a\otimes(b\otimes c)
    • 异或自反性:a\otimes b\otimes b=a\otimes 0=a
    • 对于任何数都有:x\otimes x =0x\otimes 0=x
  • &=|=>>=<<=^=:位运算的复合赋值运算符

快速幂

template <class T>
T quick_power(T x,T y){  // 求x^y
    int p = 1;
    for(int i = y; i; i >>= 1, x = x * x)
        if(i & 1) p = p * x;
    return p;
}
  • i >>= 1:即i /= 2,用于不断地向右取幂次数的二进制位。
  • i & 1:用以判断对应这一二进制是否需要进行\times x^{2^{cnt}}cnt 为要进行的幂次方数,由 x = x * x 语句决定)处理。
  • 原理即为对于任意的被幂次数都可以写为2进制形式。如13可写为1101,那么5^{13} = 5^{2^3\times1+2^2\times1+2^1\times0+2^0\times1}=5^{2^3} \times 5^{2^2}\times 5^{2^0}

  • 设最开始x值为 x,第i次循环x值为 x_i,则可以得到 x_i = x^{2^i}

ST表

ST表是一种离线查询表,用以查找特定区间内的最大(最小)值。预处理的时间复杂度为\text O(n\log n),查找时间复杂度为\text O(1),优于线段树(线段树的预处理与查找的复杂度均为\text O(n\log n))。

  • st[x][y] 用以查询区间[x,x+2^y-1]内数的最大(最小)值,也就是从 x 开始的 2^y 个数的最大(最小)值。
  • st[x][y]a[x]本身。

预处理(实例中为查找最小值的ST表)

int a[1010];//原始输入数组
int st[1010][20];//st表

void init(int n)
{
    for (int i = 0; i < n; i++)
        st[i][0] = a[i];

    for (int j = 1; (1 << j) <= n; j++)
    {
        for (int i = 0; i + (1 << j) - 1 < n; i++)
            st[i][j] = min(st[i][j - 1],st[i + (1 << (j - 1))][j - 1]);
    }
}
  • 1 << j 相当于求出2^j的值
  • \text{st}[x][y] = max/min(\text{st}[i,j-1],\text{st}[i+2^{j-1},j-1]):将[x,x+2^y-1](指序号大小,下同)分为[x,x+2^{y-1}-1][x+2^{y-1},x+2^y-1]两部分
  • 因为j是从小到大遍历的,所以在得到st[i][j]的值之前,一定会得到st[i + (1 << (j-1))][j - 1]的值

查找(实例为查找最小值)

查找区间[l,r]内的最小值:

int search(int l, int r)
{
    int k = (int)(log((double)(r - l + 1)) / log(2.0));
    return min(st[l][k],st[r - (1 << k) + 1][k]);
}
  • 有定理: 2^{\log_2 a}>\frac{a}{2} 成立。如果设 t = \log_2{len},其中 len 为从 lr 的长度(len = r-l+1),则有2^{\log_2len} > \frac{len}{2} \Rightarrow 2^t > \frac{len}{2} 成立,所以 l+2^t 跨过了区间的中间位置,那么我们可以得到 lr 的最小值是 l向前 2^k 长度区间与 r 向前 2^k 长度区间的最小值的最小值。所以区间 [l,r] 内的最小值为min(st[l][k], st[r - (1 << k) + 1][k])

LCA

  • LCA:最近公共祖先。
  • LCA 的定义可以得到:两点的 LCA 一定是两个点的祖先中深度最大的。那么也就是说两个点如果深度相同的话,他们沿着树向上走x步就可以同时到达 LCA
    • 如果深度不同,则深度较大的向上跳到深度相同的地方。
    • 如果深度相同,则一同向上跳到找到 LCA

倍增法求LCA

int lca(int a, int b){
    if(depth[a] < depth[b])
        swap(a, b);
    int c = depth[a] - depth[b];
    for(int i = 20; i >= 0;i--)
        if(c & (1 << i)) a = fa[a][i];

    // if(u == v) return u;

    for(int i = 20;i >= 0;i--)
        if(fa[a][i]!=fa[b][i])
            a = fa[a][i], b = fa[b][i];

    return fa[a][0];
}
  • 其中数组fa[a][x]表示的是对于节点a,向上跳2^x次后的父节点。这体现了倍增二分的思想。
  • i从大到小遍历,遍历到了父节点不同就将a,b转移到这个不同的节点,然后继续向上遍历。通过二分法来降低算法复杂度。

ST表求LCA

遍历编号

如上图所示的树,使用DFS遍历^*,并对每个点进行编号,得到一下序列:

A B D B E F E G E B A C A
1 2 3 2 3 4 3 4 3 2 1 2 1

^* 不同于一般的DFS遍历,这里的DFS遍历需要记录回溯走过的顶点信息。

则可以得到以下性质:两个点首次出现位置中间这一段中深度最小(也就是值最小)的即为两点的LCA。

所以我们就可以把求LCA转换为求一段序列中的最小值 → 转换为使用ST表求一段的最小值。

所使用的DFS算法如下:

int q[1000000];
top = 0;
void dfs(int u, int Fa){
    q[++top] = u, sta[u] = top;
    for(int i = 1;i <= 30;i++)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(int i = head[u];i;i = e[i].next){
        int to = e[i].to;
        if(to == Fa)
            continue;
        fa[to][0] = u;
        dfs(to, u);
    }
    q[++top] = u,end[u] = top;
}

求LCA的具体算法如下:

int lca(int a, int b){
    int ans = INT_MAX;
    begin = 0;
    for (int i = 0; i < top; i++){
        if (q[i] == a || q[i] == b){
            if(!begin)
                begin = 1;
            else break;
        }
        if (begin)
           ans = min(ans, q[i]); 
    }
    return ans;
}
转载原创文章请注明,转载自: KONGJUNE » 算法学习:倍增思想
Not Comment Found