程序员经验分享-hwhale

数据结构进阶

2023-11-14

并查集

朴素版

const int N = 1e5 + 10;

int p[N];

//返回x的祖宗节点
int find(int x){
    //只有根节点才会有p[x]=x
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

//初始化
void init(){
    //初始每个点都是根节点
    for (int i = 1; i <= n; i ++ )p[i] = i;
}

//合并a，b的两个根节点
void merge(int a, int b){
    p[find(a)] = find(b);
}

维护根节点的子元素个数

const int N = 1e5 + 10;

int p[N], size[N],n = 550;

//返回x的祖宗节点
int find(int x){
    //只有根节点才会有p[x]=x
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

//初始化
void init(){
    //初始每个点都是根节点
    for (int i = 1; i <= n; i ++ ){
        p[i] = i;
        size[i] = 1;
    }
}

//合并a，b的两个根节点
void merge(int a, int b){
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);
}

维护到祖宗节点距离的并查集

const int N = 1e5 + 10;

int p[N], d[N],n = 550;

//返回x的祖宗节点
int find(int x){
    //只有根节点才会有p[x]=x
    if(p[x] != x) {
        int u = find(p[x]);
        //当前节点要加上父节点的距离
        d[x] += d[p[x]];
        p[x] = u;
    }
    return p[x];
}

//初始化
void init(){
    //初始每个点都是根节点
    for (int i = 1; i <= n; i ++ ){
        p[i] = i;
        d[i] = 0;
    }
}

//合并a，b的两个根节点
void merge(int a, int b){
    d[find(a)] = 1; // 根据具体问题，初始化find(a)的偏移量
    p[find(a)] = find(b);
}

树状数组

树状数组基本用途是维护序列的前缀和。对于给定序列a，我们建立一个数组c，其中c[x]保存序列a的区间[x-lowbit(x) + 1, x]中所有数的和，即 ∑ i = x − l o w b i t ( x ) + 1 x a [ i ] \sum_{i=x-lowbit(x)+1}^{x}a[i] ∑i=x−lowbit(x)+1x​a[i]。

在这里插入图片描述

树状数组的前缀和

//返回1-k的前缀和
int ask(int x){
	int ans = 0;
	for(;x > 0; x -= (x & - x)) ans += c[x];
	return ans;
}
//返回区间[l,r]的和
int getSum(int l, int r){
	return ask(r) - ask(l - 1);
}

树状数组的单点增加

//给序列中的一个数a[x]加上y
void add(int x, int y){
	for(; x<= N; x += (x & -x)) c[x] += y;
}

树状数组的初始化

直接建立一个全为0的数组c，然后堆每个位置执行add(x,a[x])。就完成了堆原始序列a构造数组数组的过程。时间复杂度 O ( N l o g N ) O(NlogN) O(NlogN)

更高效的方法是：从小到大依次考虑每个节点x，借助 l o w b i t lowbit lowbit运算扫描它的子节点并求和。时间复杂度O(N)

线段树

线段树是一种基于分治思想的二叉树结构，用于区间上进行信息统计。

  1. 线段树的每个节点都代表一个区间
  2. 线段树具有唯一的根节点，代表的区间是整个统计范围，如 [ 1 , N ] [1,N] [1,N]
  3. 线段树的每个叶节点都代表一个长度为1的元区间[x,x]
  4. 对于每个内部节点 [ l , r ] [l,r] [l,r]，它的左子节点是 [ l , m i d ] [l,mid] [l,mid]，右子节点是 [ m i d + 1 , r ] [mid+1,r] [mid+1,r]，其中 m i d = ( l + r ) / 2 ( 向 下 取 整 ) mid=(l+r)/2(向下取整) mid=(l+r)/2(向下取整)

在这里插入图片描述

如何保存线段树

上图展示了一颗线段树。可以发现，出去树的最后一层，整棵线段树一定是一棵完全二叉树，树的深度为 O ( l o g N ) O(logN) O(logN)。因次可用二叉堆类似的"父子2倍的"节点编号方法：

  1. 根节点编号为1
  2. 编号为 x x x的节点的左子节点编号为 x ∗ 2 x*2 x∗2，右子节点编号为 x ∗ 2 + 1 x*2+1 x∗2+1。
  3. N N N个叶节点的满二叉树有 N + N / 2 + N / 4 + . . . + 2 + 1 = 2 N − 1 N+N/2+N/4+...+2+1=2N-1 N+N/2+N/4+...+2+1=2N−1个节点。因为在上述存储方式下，最后一层还产生空余，所以保存线段树的数组长度要不小于 2 N + 2 N = 4 N 2N+2N=4N 2N+2N=4N

线段树的建树

线段树的基本用途是对序列进行维护，支持查询和修改指令。给定一个长度为 N N N的序列A。我们可以在区间[1,N]上建立一颗线段树，每个叶节点[i,i]保存A[i]的值。线段树的二叉树结构可以很方便地从下往上传递信息。以区间问题最大值问题为例，记 d a t ( l , r ) dat(l,r) dat(l,r)等于 m a x l < = i < = r { A [ i ] } max_{l<=i<=r}\{A[i]\} maxl<=i<=r​{A[i]}，显然 d a t ( l , r ) = m a x ( d a t ( l , m i d ) , d a t ( m i d + 1 , r ) ) dat(l,r)=max(dat(l,mid), dat(mid+1,r)) dat(l,r)=max(dat(l,mid),dat(mid+1,r))

在这里插入图片描述

struct Node{
    int l, r;
    int dat;
} t[N * 4];

void build(int p, int l, int r){
    //节点p代表区间[l,r]
    t[p].l = l, t[p].r = r;
    //找到叶节点，赋值
    if(l == r){
        t[p].dat = a[l]; 
        return;
    }
    //折半
    int mid = l + r >> 1;
    //左子节点,区间[l,mid]
    build(p*2, l, mid);
    //右子节点，区间[mid + 1, r]
    build(p *2 + 1, mid  + 1, r);
    //从子节点返回了
    //利用左右子节点更新当且节点的信息
    t[p].dat = max(t[p*2].dat, t[p*2 + 1].dat);
}
build(1,1,n);//调用入口

线段树的单点修改

在线段树中，根节点（编号为1的节点）是执行各种指令的入口。我们需要从根节点出发，递归找到代表区间[x,x]的叶节点，然后从下往上更新[x,x]及其它的祖先节点

// p：线段树的节点，x：数组a中要修改的位置，v：要修改的值
void change(int p, int x, int v){
    //找到叶子节点，更新叶子节点的值
    if(t[p].l == t[p].r){
        t[p].dat = v;
        return;
    }
    int mid = (t[p].l, t[p].r) >> 1;
    //x
    if(x <= mid) change(p*2, x, v);
    else change(p*2  + 1, x, v);
    //从下往上更新信息
    t[p].dat = max(t[p*2].dat, t[p*2+1].dat);
}

在这里插入图片描述

线段树的区间查询

查询序列A在区间 [ l , r ] [l,r] [l,r]上的最大值

  1. 若 [ l , r ] [l,r] [l,r]完全覆盖了当且节点代表的区间，即立即回溯，并且该节点的dat值为候选答案。
  2. 若左子节点与 [ l , r ] [l,r] [l,r]有重叠部分，则递归访问左子节点。
  3. 若右子节点与 [ l , r ] [l,r] [l,r]有重叠部分，则递归访问右子节点。
int ask(int p, int l, int r){
    //当前区间被[l,r]完全包含，立即返回
    if(l <= t[p].l && r>= t[p].r) return t[p].dat;
    int mid = t[p].l + t[p].r >> 1;
    //负无穷大
    int val = -1e9;
    //左子节点有重叠
    if(l <= mid) val = max(val, ask(p*2, l, r));
    //右子节点有重叠
    if(r > mid) val = max(val, ask(p*2+1, l, r));
    return val;
}

在这里插入图片描述

二叉查找树与平衡树初步

BST(Binary Search Tree)

给定一颗二叉树，树上每一个节点都带有一个数值，称为节点的“关键码”(key)。对于树中任意一个节点

  1. 该节点的key大于等于它的左子树任意节点的key
  2. 该节点的key小于等于它的右子树任意节点的key

满足上述性质的二叉树就是二叉查找树，二叉查找树的中序遍历是一个key单调递增的节点序列

BST的初始化

为了避免越界冲突，减少边界情况的特殊判断，在BST中额外插入一个key为正无穷和一个key为负无穷的节点。仅有这两个节点构成的BST就是一颗初始的空BST

const int N = 1e5 + 10;

struct BST{
    int l, r;
    int val;
} a[N];

int tot = 0, root, INF= 1e9;

int newOne(int val){
    a[++tot].val = val;
    return tot;
}

void build(){
    for (int i = 0; i < N; i ++ ){
        a[i].l = 0;
        a[i].r = 0;
    }
    newOne(-INF), newOne(INF);
    //根节点是负无穷，根节点的右子节点是正无穷
    root = 1, a[1].r = 2;
}

BST的检索

在BST中检索是否存在key为val的节点
变量p为根节点root，执行以下过程

  1. 若p.key == val，找到并返回
  2. 若p.key > val，若左子节点为空，说明不存在该val.；否则在p的左子树递归进行检索
  3. 若p.key<val，若右子节点为空，说明不存在该val.；否则在p的右子树递归进行检索
    在这里插入图片描述 
//若存在返回>0得到数
int get(int p, int val){
    //检索失败
    if(p == 0) return 0;
    if(val == a[p].val) return p;
    return val < a[p].val ? get(a[p].l, val) : get(a[p].r, val);
}

BST的插入

与BST的检索过程类似，在发现p的子节点为空，说明val不存在，直接建立key为val的新节点作为p的子节点
在这里插入图片描述

void insert(int &p, int val){
    if(p == 0){
        //找到为空的节点。创建并赋值
        p = newOne(val);
        return;
    }
    if(val == a[p].val) return;
    if(val < a[p].val) insert(a[p].l, val);
    else insert(a[p].r, val);
}

BST求前驱/后继

前驱：所有小于指定值中最大的一个
后继：所有大于指定值中最小的一个

求后继

  1. 初始化ans为key为正无穷的节点编号。然后，在BST中检索val，每经过一个点，都检查该节点的key，判断能否更新所求的ans
  2. 检索完成有三种结果
  3. 没有找到val，此时val的后继就已经在经过的节点中，ans即为所求，
  4. 找到了key为val的节点p，但p没有右子树，ans即为所求
  5. 找到了key为val的节点p，p有右子树。从p的右子节点出发，一直向左走，就找到了val的后继
int getNext(int val){
    int ans = 2;
    int p = root;
    while (p > 0){
        if(val == a[p].val){
            if(a[p].r > 0){
                //走到右子树
                p = a[p].r;
                //从右子树一直往左走
                while (a[p].l > 0) p = a[p].l;
                ans = p;
            }
            break;
        }
        //每经过一个节点，都尝试更新后继
        //如果前节点的val大于参数的val并且当前节点的val小于当前答案的val，更新答案
        if(a[p].val > val && a[p].val < a[ans].val) ans = p;
        //若当前节点的val大于参数的val，向左子树走，否则向右子树走
        p = val < a[p].val ? a[p].l : a[p].r;
    }
    return ans;
}

求前驱

int getPrev(int val){
    //负无穷小的节点
    int ans = 1;
    int p = root;
    while (p > 0){
        if(val == a[p].val){
            //有左子树
            if(a[p].l > 0){
                //走到左子树
                p = a[p].l;
                //从左子树一直往右走
                while (a[p].r > 0) p = a[p].r;
                ans = p;
            }
            break;
        }
        //每经过一个节点，都尝试更新前驱
        //如果前节点的val小于参数的val并且当前节点的val大于当前答案的val，更新答案
        if(a[p].val < val && a[p].val > a[ans].val) ans = p;
        //若当前节点的val小于参数的val，向右子树走，否则向左子树走
        p = val > a[p].val ? a[p].r : a[p].l;
    }
    return ans;
}

BST的节点删除

1. 在BST中检索val，得到节点p
2. 若p的子节点个数小于2，直接删除p，并令p的子节点代替p的位置，与p的父节点相连
3. 若p既有左子树又有右子树，则在BST中求出val的后继节点next。因为next没有左子树，所以可以直接删除next，并令next的右子树代替next的位置，最后，再让next节点代替p节点，删除p即可

//从子树p中删除值为val的节点
//p:子树的节点，val：值
//注意p是引用
void rm(int &p, int val){
    //检索边界
    if(p == 0) return;
    //检索边界
    if(val == a[p].val){
        //检索到指定值val
        if(a[p].l == 0){
            //左子树为空，让右子树代替当前节点
            p = a[p].r;
        }else if(a[p].r == 0){
            //右子树为空，让左子树代替当前节点
            p = a[p].l;
        }else{
            //寻找后继节点，从右子树一直往左走
            int next = a[p].r;
            while(a[next].l > 0) next = a[next].l;
            //val的后继节点一定没有左子树
            //从当前节点的右子树删除后继节点
            rm(a[p].r, a[next].val);
            //令后继节点代替节点p的位置
            a[next].l = a[p].l, a[next].r = a[p].r;
            p = next;
        }
        return;
    }
    //检索过程
    if(val < a[p].val){
        rm(a[p].l, val);
    }else{
        rm(a[p].r, val); 
    }
}

Treap

BST很容易退化，插入从小到大序列会让BST操作复杂度退化成O(n)。Treap是入门的平衡树，通过旋转改变二叉树的形态，且保持BST的性质

改变形态并保持BST性质的方法是旋转，最基本的旋转操作称为单旋转，单旋转又分为左旋和右旋。
在这里插入图片描述

以右旋为例子。在初始情况下，x是y的左子节点，A和B分别为是x的左右子树，C是y的右子树。右旋操作在保持BST的性质的基础上，把x变为y’的父节点。因为x的key小于y的key，所以应该作为x的右子节点。当x变成y的父节点后，y的左子树就空了出来，于是x原理的右子树B就恰好做为y的左子树。

zig (p)可以理解为把p的左子节点绕着p向右旋转

void zig(int p){
    int q = a[p].l;
    a[p].l = a[q].r, a[q].r = p;
    p = q;
}

zag(p)可以理解为把p的右子节点绕着p向左旋转

void zag(int &p){
    int q = a[p].r;
    a[p].r = a[q].l, a[q].l = p;
    p = q;
}

acwing253

//副本数cnt解决重复关键值的问题，增加时cnt+1，减少时cnt-1，为0时删除
//size统计每个根的副本数，解决排名问题
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
struct Treap{
    int l, r;
    int val, dat; //key，权值
    int cnt, size; //副本数，子树大小
} a[N];

int tot, root, n, INF = 0x7fffffff;

int newOne(int val){
    //把值存起来
    a[++tot].val = val;
    //随机权值
    a[tot].dat = rand();
    //副本数为1，以该节点为根的总副本数为1（没有左右子节点）
    a[tot].cnt = a[tot].size = 1;
    return tot;
}

//更新size
void update(int p){
    //size = 左子节点的size + 右子节点的size + 当前节点的副本数
    a[p].size = a[a[p].l].size + a[a[p].r].size + a[p].cnt;
}

//构建Treap
void build(){
    newOne(-INF),newOne(INF);
    root = 1, a[1].r = 2;
    update(root);
}

//根据值获取排名
int getRankByVal(int p, int val){
    if(p == 0) return 0;
    //相等就返回左子树的size, +1代表p自己
    if(val == a[p].val) return a[a[p].l].size + 1;
    //val小于当前节点的值, 统计左子的排名
    if(val < a[p].val) return getRankByVal(a[p].l, val);
    //右子节点的排名 + 左子节点的排名 + 自己的副本数
    return getRankByVal(a[p].r, val) + a[a[p].l].size + a[p].cnt;
}

//根据排名获取值
int getValByRank(int p, int rank){
    if(p == 0) return INF;
    if(a[a[p].l].size >= rank) return getValByRank(a[p].l, rank);
    if(a[a[p].l].size + a[p].cnt >= rank) return a[p].val;
    return getValByRank(a[p].r, rank - a[a[p].l].size - a[p].cnt);
}

void zag(int &p){
    int q = a[p].r;
    a[p].r = a[q].l, a[q].l = p, p = q;
    update(a[p].l), update(p);
}

void zig(int &p){
    int q = a[p].l;
    a[p].l = a[q].r, a[q].r = p, p = q;
    update(a[p].r), update(p);
}

void insert(int &p, int val){
    if(p == 0){
        p = newOne(val);
        return;
    }
    if(val == a[p].val){
        a[p].cnt++,update(p);
        return;
    }
    if(val < a[p].val){
        insert(a[p].l, val);
        if(a[p].dat < a[a[p].l].dat) zig(p);
    }else{
        insert(a[p].r, val);
        if(a[p].dat < a[a[p].r].dat) zag(p);
    }
    update(p);
}

int getPrev(int val){
    int ans = 1;
    int p = root;
    while(p > 0){
        if(val == a[p].val){
            if(a[p].l > 0){
                p = a[p].l;
                while(a[p].r > 0) p = a[p].r;
                ans = p;
            }
            break;
        }
        if(a[p].val < val && a[p].val > a[ans].val) ans = p;
        p = val < a[p].val ? a[p].l: a[p].r;
    }
    return a[ans].val;
    
}

int getNext(int val){
    int ans = 2;
    int p = root;
    while(p > 0){
        if(val == a[p].val){
            if(a[p].r > 0){
                p = a[p].r;
                while(a[p].l > 0) p = a[p].l;
                ans = p;
            }
            break;
        }
        if(a[p].val > val && a[p].val < a[ans].val) ans = p;
        p = val < a[p].val ? a[p].l: a[p].r;
    }
    return a[ans].val;
}

void rm(int &p, int val){
    if(p == 0) return;
    if(val == a[p].val){
        if(a[p].cnt > 1){
            a[p].cnt --, update(p);
            return;
        }
        if(a[p].l || a[p].r){
            if(a[p].r == 0 || a[a[p].l].dat > a[a[p].r].dat) {
                zig(p),rm(a[p].r, val);
            }else{
                zag(p), rm(a[p].l, val);
            }
            update(p);
        }else p = 0;
        return;
    }
    val < a[p].val ? rm(a[p].l, val) : rm(a[p].r, val);
    update(p);
}

int main()
{
    build();
    cin >> n;
    while (n -- ){
        int opt, x;
        scanf("%d%d", &opt, &x);
        switch(opt){
            case 1:
                insert(root, x);
                break;
            case 2:
                rm(root, x);
                break;
            case 3:
                printf("%d\n", getRankByVal(root, x) - 1);
                break;
            case 4:
                printf("%d\n", getValByRank(root, x + 1));
                break;
            case 5:
                printf("%d\n", getPrev(x));
                break;
            case 6:
                printf("%d\n", getNext(x));
                break;
        }
    }
    
}

可持久化数据结构

可持久化Trie

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

算法

LeetCode

数据结构进阶 的相关文章

随机推荐

  • sklearn与分类算法

    导读 众所周知 Scikit learn 以前称为 scikits learn 是一个用于 Python 编程语言的免费软件机器学习库 它具有各种分类 回归和聚类算法 包括支持向量机 随机森林 梯度增强 k means 和 DBSCAN 旨

  • Golang 数据结构 —— 字典

    Golang 数据结构 字典 字典存储 key value 对 Go提供了非常方便的实现 内置的map类型 本文增强内置的map类型 添加便捷的操作用于获取或改变其内容 创建ItemDictionary泛型 并发安全的 能够生成任何具体类型

  • linux配置svn 版本管理之创建仓储和权限管理

    1 安装 yum install subversion 2 配置 2 1 创建仓库 我们这里在 home下建立一个名为svn的仓库 repository 以后所有代码都放在这个下面 创建成功后在svn下面多了几个文件夹 root local

  • 拉链表的设计与实现

    一 什么是拉链表 针对订单表 订单商品表 流水表 这些表中的数据是比较多的 如果使用全量的方式 会造成大量的数据冗余 浪费磁盘空间 所以这种表 一般使用增量的方式 每日采集新增的数据 在这注意一点 针对订单表 如果单纯的按照订单产生时间增量

  • 前台想后台传数组与解析

    var info JSON stringify ids ajax type POST url url data ids info flowId flowId flowName flowName name name html html dat

  • 多数据源的配置

    一 yml的数据源配置 配置两个数据源一个叫master主数据源 一个是slave从数据源 默认是主数据源 从数据源需要做切换 datasource master driver class name com microsoft sqlser

  • 2023年苹果IOS开发者证书申请（已实测准确）

    一 创建苹果开发者账号 苹果开发者官网 https developer apple com 注册苹果账号apple id 开启双重认证 需在一台IOS手机 iPad操作 在App Store下载Apple Developer APP 进行注

  • 怎么关闭csv的科学计数法

    一 问题背景 身份证号码 订单号这些都是很长的字符串 在csv文件中经常以科学计数法出现 要取消科学计数法 二 解决方案 笔者的方案最终是以xls格式保存下来 如果大家需要以csv文件格式保存 那么笔者的解决方案是无效的 而且有必要了解一点

  • 外网SSH远程连接linux服务器，看这一篇就够了

    文章目录 视频教程 1 Linux CentOS安装cpolar 2 创建TCP隧道 3 随机地址公网远程连接 4 固定TCP地址 5 使用固定公网TCP地址SSH远程 转载自内网穿透工具的文章 无公网IP SSH远程连接Linux Cen

  • Django：四、Djiango如何连接使用MySQL数据库

    一 安装数据库第三方插件 安装下载mysql第三方插件 pip install mysqlclient 二 创建MySQL数据库 ORM可以帮助我们做两件事 创建 修改 删除数据库中的表 不用写SQL语句 但无法创建数据库 操作表中的数据

  • 踩坑解决：web Server Traceback(most recent call last)builtins. Attributeerror: int object has no attribut

    解决方法 尝试将Twisted 版本重新安装成 18 9 0 卸载Twisted命令 pip uninstall Twisted 安装指定版本Twisted pip install Twisted 18 9

  • centos7 合并pdf命令

    格式 命令行 要合并文件 合并后的文件名 pdfunite pdf all pdf pdfunite 1 pdf 2 pdf all pdf

  • 已解决ERROR: No matching distribution found for gradio==3.23

    已解决stderr ERROR Could not find a version that satisfies the requirement gradio 3 23 ERROR No matching distribution found

  • C/C++就业方向与技能需求整理-实习篇

    前言 本文主要面向计算机类本科生同时想要寻求偏向C 相关的职业 提供就业方向参考以及需要学习的技能 以下资料来自牛客网 更于 2022 4 1 网络研发实习生 岗位职责 1 通过软件开发实现数据中心网络和骨干网络的管理和运维自动化 确保网络

  • 安装centos7报错：/dev/root does not exist 问题处理过程

    最近自己做练习的一台实体机服务器硬盘坏了 想着换了重新装一下 结果就是碰壁 折腾了好几天 一直以为是写U盘的工具有问题 报的错也是奇怪 提示 dev root does not exist 并且前面出现n排同样的警告 Warning dra

  • 用Java写一个公司员工管理系统!

    用Java写一个公司员工管理系统 今天看CSDN发现写管理系统的文章不少 我在这里也给大家用java写一篇 当然这里只是最简单的那种qwq 核心功能 对员工各项信息的管理 采用属性文件 资源文件 支持中文简体和英文 目录 第一步 创建一个记

  • 李宏毅 深度学习作业3 CNN

    通过CNN卷积神经网络对食物图片进行分类 训练集与验证集中图片格式为 类别 编号 jpg Import 需要的套件 import os import numpy as np import cv2 import torch import to

  • mysql aio与并发执行线程_mysql 原理 ~ 线程与IO

    一 简介 今天来聊聊具体的线程和IO 二 具体线程与作用 1 master thread mysql的主要工作触发线程 1 redo and binlog日志 2 合并插入缓冲 3 脏页的刷新 4 undo页回收 5 产生一个ckp点 2

  • 从Python到计算机视觉：入门指南

    Python一直是计算机科学领域中最受欢迎的语言之一 它不仅易于学习和使用 而且具有广泛的应用领域 尤其是计算机视觉方面 本文将为读者提供一份详细的入门指南 帮助初学者了解Python和计算机视觉的基础知识和应用 安装Python 要开始使

  • 数据结构进阶

    并查集 朴素版 const int N 1e5 10 int p N 返回x的祖宗节点 int find int x 只有根节点才会有p x x if p x x p x find p x return p x 初始化 void init

热门标签