分类 算法 下的文章
算法笔记 | 康托展开及其逆运算
perm_identity  query_builder
list文章,算法  comment评论
康托展开

康托展开是一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩.
而对于一个序列,其所有排列按照字典序排序的顺序从小到大编号, 康拓展开就是用于计算这种排列在其顺序中的位置.

举个栗子╰(°▽°)╯
对于序列{1,3,2}, 它的顺序位于其所有排列的第2位, 前一位为{1,2,3}.

其公式如下:
cantor.png
其中 T 为其排列的顺序, A_i 为序列中第 i 个元素, n 为序列总长度.

我们可以看到, 其中需要计算n!, 这一步可以通过打表来优化时间复杂度, 而当n!过大的时候, 就需要大整数计算了.

康托展开的逆运算

因为康托展开是一个双射, 那么一个合法的 T 值必定对应一个唯一的序列, 也就是说可以反向计算顺序为 T 的序列.


1.输入n, T
2.计算第i位对应的值(i从1开始):
    a)将T-1,意为前面有T-1个排列
    b)currI = T/(n-i)!, currI即为当前位数
    c)如果currI已经被使用过,那么currI++
    d)currM = T%(n-i)!, currM为剩下的数
    e)T = currM
3.输出所有的currI

那么直接来道题叭:CodeVS 2972 - 选课

但是这道题...数据并不是很强...只有三个监测点

资料参考 Joseph Galante:Generalized Cantor Expansions


算法笔记 | 从零开始的线段树
perm_identity  query_builder
list文章,算法  comment评论

线段树(Segment tree) 即解决区间问题的数据结构 常用于算法竞赛中
可以说是一种典型以空间换取时间的数据结构

举个栗子

区间求和问题
给定 n 个数,将会有 m 次操作
每次进行以下两种操作其中的一种:

  • 求出区间 (l,r) 内所有数的加和
  • 将位置 i 上的数增加 x

数据范围:

  • 1 <= n <= 100000
  • 1 <= l <= r <= 100000
  • 1 <= m <= 10000

时间:1000MS 空间限制:128000KB

题目链接:CodeVS 1080 线段树练习

朴素做法

就是很简单的去维护一个一维数组
每次求和操作对数组 arr[l],arr[l+1]....,arr[r] 相加处理,时间复杂度 O(m)
每次增加操作直接修改 arr[x] 时间复杂度 O(1)
最极端的情况下这道题目的时间复杂度就变成了 O(m*n)
肯定是过不去的...所以这个时候就要介绍我们今天的主角线段树了

线段树

首先看到线段树,其实我是拒绝的...
因为直接看代码的话,神仙们写的代码一个人一种写法...

先介绍一下线段树的简单实现(我知道我讲话水平不好...所以文字描述看不懂的话请结合图片和代码来看):

线段树是一颗完全二叉树
我们给定一个节点存储区间(l,r)的信息
那么这个节点的左儿子则记录区间(l,(l+r)/2)的信息 右儿子记录了区间((l+r)/2+1,r)的信息

实现这个数据存储的过程 就是一个建树的过程

首先让我们先定义一下各个函数以及所用到的变量

//宏定义方便写代码 其中 << 为位运算 <<1 相当于乘二 <<1|1相当于乘二加1
#define leftSon left,mid,curr<<1
#define rightSon mid+1,right,curr<<1|1

long long int arrSum[maxN << 2];    //使用O(4*n)的空间建树

//更新当前节点的区间和
void pushUp(int curr);
//递归建树
void buildTree(int left, int right, int curr);
//对节点 node 增加 value
void addNode(int node, int value, int left, int right, int curr);
//查询区间(leftSection,rightSection)的和
unsigned long long int querySection(int leftSection, int rightSection, int left, int right, int curr);

让我们先来模拟递推一下线段树的构建过程
首先我们将数据读入 记作原数组Array

1.png

结合题意 我们需要求的区间的和 所以节点的记录的信息就是区间的和
既有以下的结构

2.png

此时让我们思考两个问题:

  1. 如何快速简便的建立线段树
  2. 如果题目给出的数据不满足2^n 那么如何建树

这个时候就要介绍一下二叉树的数组表示方法 也是在算法竞赛中常用到的方法

3.png

通过对图的观察可以知道 对于父亲节点arrSum[x] 它的左儿子即为arrSum[x<<1] 右儿子为arrSum[x<<1|1]
此时对于这道题线段树中的任意节点arrSum[x],它的值就是arrSum[x<<1]+arrSum[x<<1|1] 也就是一个从底向上递推当前区间和的过程
而利用这种方法建树 在之后的查询更新过程中利用这种性质也规避数据不满足 2^n 时访问越界的情况
这个时候就可以写出pushUp函数了

//pushUp向上更新节点(更新curr节点的值为它的两个儿子的加和)
void pushUp(int curr) {
    arrSum[curr] = arrSum[curr << 1] + arrSum[curr << 1 | 1];
    return;
}

之后利用递归来建树 先递归到树的最下面 之后更新上一层的节点
此时建树的时间复杂度是O(nlogn)
4.png

//这里我的习惯写法是在线地去建树 直接去掉了文中的Array数组
//建树函数 left为当前的左区间 right为当前的右区间 curr为当前对应的数组下标(节点)
//调用的话就是buildTree(1,n,1) 意味着建立一个(1,n)区间的线段树 当前的数组下标(节点)为1
void buildTree(int left, int right, int curr) {
        //先计算出中值 方便后续的二分
    int mid = (left + right) >> 1;
        //如果当前的左区间等于右区间,也就是满足了(x,x)的情况,获取第x个数据并存放于对应的节点中
    if (left == right) {
        scanf("%lld", &arrSum[curr]);
        return;
    }
        //递归建左右的节点
    buildTree(leftSon);
    buildTree(rightSon);
        //建完子树之后使用pushUp函数更新当前节点的值(区间和)为左右儿子节点的加和
    pushUp(curr);
    return;
}

接下来就是对位置 i 上的数进行更改,这个过程类似于建树的过程,查找这个节点是在当前的左或者右区间上,然后二分,直到到对应的位置上,对其进行加减操作之后,在递归的过程中向上pushUp,更新对应节点的值
时间复杂度为O(logn)

5.png

//对位置为node的节点增加value的值 等同于对区间(node,node)增加value的值
//调用方法就是addNode(node,value,1,n,1)
void addNode(int node, int value, int left, int right, int curr) {
    int mid = (left + right) >> 1;
        //如果左区间等于右区间 已经到达位置 对节点进行相加操作
    if (left == right) {
        arrSum[curr] += value;
        return;
    }
        //判断要操作的节点node在自己的左右区间 并进行二分
    if (node <= mid)
        addNode(node, value, leftSon);
    else
        addNode(node, value, rightSon);
        //儿子节点已经更新完了 用新的儿子节点的数据来更新当前节点的值 注意这是一个递归的函数
    pushUp(curr);
    return;
}

接下来也就是最后一个操作了
查询区间(l,r)
时间复杂度是O(logn)

6.png

//查询区间(leftSection,rightSection)
long long int querySection(int leftSection, int rightSection, int left, int right, int curr) {
    int mid = (left + right) >> 1;
        //如果当前区间在查询范围内 返回当前区间的值
    if (leftSection <= left && right <= rightSection)
        return arrSum[curr];
    long long int ret = 0;
        //判断查询区间的范围在当前区间的左或者右侧 二分
    if (leftSection <= mid)
        ret += querySection(leftSection, rightSection, leftSon);
    if (rightSection > mid)
        ret += querySection(leftSection, rightSection, rightSon);
        //返回当前已经查询到的值
    return ret;
}

最后 附上AC代码

Accepted 46ms 2 MB

/**
 * @author    Moe_Sakiya        sakiya@tun.moe
 * @date        2018-04-08 20:43:37
 *
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

#define leftSon left,mid,curr<<1
#define rightSon mid+1,right,curr<<1|1

const int maxN = 100005;

long long int arrSum[maxN << 2];

void pushUp(int curr) {
    arrSum[curr] = arrSum[curr << 1] + arrSum[curr << 1 | 1];
    return;
}

void buildTree(int left, int right, int curr) {
    int mid = (left + right) >> 1;
    if (left == right) {
        if(left==9)
            printf("[%d]\n",curr );
        scanf("%lld", &arrSum[curr]);
        return;
    }
    buildTree(leftSon);
    buildTree(rightSon);
    pushUp(curr);
    return;
}

void addNode(int node, int value, int left, int right, int curr) {
    int mid = (left + right) >> 1;
    if (left == right) {
        arrSum[curr] += value;
        return;
    }
    if (node <= mid)
        addNode(node, value, leftSon);
    else
        addNode(node, value, rightSon);
    pushUp(curr);
    return;
}

long long int querySection(int leftSection, int rightSection, int left, int right, int curr) {
    int mid = (left + right) >> 1;
    if (leftSection <= left && right <= rightSection)
        return arrSum[curr];
    long long int ret = 0;
    if (leftSection <= mid)
        ret += querySection(leftSection, rightSection, leftSon);
    if (rightSection > mid)
        ret += querySection(leftSection, rightSection, rightSon);
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int i, n, q, arg1, arg2, arg3;
    scanf("%d", &n);
    buildTree(1, n, 1);
    scanf("%d", &q);
    for (i = 0; i < q; i++) {
        scanf("%d", &arg1);
        switch (arg1) {
        case 1:
            scanf("%d %d", &arg2, &arg3);
            addNode(arg2, arg3, 1, n, 1);
            break;
        case 2:
            scanf("%d %d", &arg2, &arg3);
            printf("%lld\n", querySection(arg2, arg3, 1, n, 1));
            break;
        }
    }
    return 0;
}