常用代码模板2（2）——数据结构

亦凉 2024-03-26 14:38 42阅读 0赞

## 常用代码模板2（2）——数据结构 ##

原文：[常用代码模板2——数据结构][2]

### Trie树 ###

`高效存储和查找字符串集合`的数据结构

int son[N][26], cnt[N], idx;
    // 0号点既是根节点，又是空节点
    // son[][]存储树中每个节点的子节点
    // cnt[]存储以每个节点结尾的单词数量
    
    // 插入一个字符串
    void insert(char *str)
    {
        int p = 0;
        for (int i = 0; str[i]; i ++ )
        {
            int u = str[i] - 'a';
            if (!son[p][u]) son[p][u] = ++ idx;
            p = son[p][u];
        }
        cnt[p] ++ ;
    }
    
    // 查询字符串出现的次数
    int query(char *str)
    {
        int p = 0;
        for (int i = 0; str[i]; i ++ )
        {
            int u = str[i] - 'a';
            if (!son[p][u]) return 0;
            p = son[p][u];
        }
        return cnt[p];
    }

### 并查集 ###

*  将两个集合合并
 *  询问两个元素是否在一个集合中

(1)朴素并查集：
    
        int p[N]; //存储每个点的祖宗节点
    
        // 返回x的祖宗节点
        int find(int x)
        {
            if (p[x] != x) p[x] = find(p[x]);
            return p[x];
        }
    
        // 初始化，假定节点编号是1~n
        for (int i = 1; i <= n; i ++ ) p[i] = i;
    
        // 合并a和b所在的两个集合：
        p[find(a)] = find(b);
    
    
    (2)维护size的并查集：
    
        int p[N], size[N];
        //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
    
        // 返回x的祖宗节点
        int find(int x)
        {
            if (p[x] != x) p[x] = find(p[x]);
            return p[x];
        }
    
        // 初始化，假定节点编号是1~n
        for (int i = 1; i <= n; i ++ )
        {
            p[i] = i;
            size[i] = 1;
        }
    
        // 合并a和b所在的两个集合：
        size[find(b)] += size[find(a)];
        p[find(a)] = find(b);
    
    
    (3)维护到祖宗节点距离的并查集：
    
        int p[N], d[N];
        //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
    
        // 返回x的祖宗节点
        int find(int x)
        {
            if (p[x] != x)
            {
                int u = find(p[x]);
                d[x] += d[p[x]];
                p[x] = u;
            }
            return p[x];
        }
    
        // 初始化，假定节点编号是1~n
        for (int i = 1; i <= n; i ++ )
        {
            p[i] = i;
            d[i] = 0;
        }
    
        // 合并a和b所在的两个集合：
        p[find(a)] = find(b);
        d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

### 堆 ###

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
    // ph[k]存储第k个插入的点在堆中的位置
    // hp[k]存储堆中下标是k的点是第几个插入的
    int h[N], ph[N], hp[N], size;
    
    // 交换两个点，及其映射关系
    void heap_swap(int a, int b)
    {
        swap(ph[hp[a]],ph[hp[b]]);
        swap(hp[a], hp[b]);
        swap(h[a], h[b]);
    }
    
    void down(int u)
    {
        int t = u;
        if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
        if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
        if (u != t)
        {
            heap_swap(u, t);
            down(t);
        }
    }
    
    void up(int u)
    {
        while (u / 2 && h[u] < h[u / 2])
        {
            heap_swap(u, u / 2);
            u >>= 1;
        }
    }
    
    // O(n)建堆
    for (int i = n / 2; i; i -- ) down(i);

[2]: https://www.acwing.com/blog/content/404/