并查集

并查集主要是为了解决动态连通性问题，这里主要是利用了一个技巧，就是用一个数组来表示连通的集合。这样，合并就抽象为将一个集合的值变为另一个集合。判断两个变量是否连通抽象为两个变量是否属于同一个集合。这里的实现是使用一个数组来记录父节点，如果父节点是本身，那么这个值就代表一个集合。这里进行了一点优化，就是在合并的时候，将小树合并到大树。

class UnionFind{
public:
    UnionFind(int n):cnt(n){
        for(int i=0;i<n;i++){
            id.push_back(i);
            size.push_back(1);
        }
    }

    int find(int p){
        while(p != id[p]){
            p = id[p];
        }
        return p;
    }

    void merge(int p, int q){
        int i = find(p);
        int j = find(q);
        if(i == j){
            return;
        }
        if(size[i] < size[j]){
            id[i] = j;
            size[j] += size[i];
        }else{
            id[j] = i;
            size[i] += size[j]; 
        }
        cnt--;
    }

    int count(){
        return cnt;
    }

private:
    vector<int> id;
    vector<int> size;
    int cnt;
};

字典树

字典树的实现个人认为还是比较简单，主要是递归的应用，其实这里是可以不使用递归的，但是为了简单起见，使用递归可以使得思路更加清晰。这里需要注意的一点是，使用连接代表字母，而不是使用结点代表字母；结点只是表示从root到该结点的之间组成的单词是否存在。

class Trie {
public:
    Trie():root(NULL){}

    ~Trie(){
        delete root;
    }

    void insert(string word) {
        root = put(root,word,0);
    }
    
    bool search(string word) {
        return get(root,word,0);
    }
    
    bool startsWith(string prefix) {
        return find(root,prefix,0);
    }

    void delWord(string word){
        root = del(root,word,0);
    }

private:
    class Node{
    public:
        Node():isEnd(false){
            for(int i=0;i<26;i++){
                child[i] = NULL;
            }
        }
        ~Node(){
            for(int i=0;i<26;i++){
                if(child[i] != NULL){
                    delete child[i];
                }
            }
        }
        Node *child[26];
        bool isEnd;
    };

    Node *root;

    Node* put(Node *node, string word, int n){
        if(node == NULL){
            node = new Node();
        }    
        if(n == word.size()){
            node->isEnd = true;
        }else{
            int pos = word[n] - 'a';
            node->child[pos] = put(node->child[pos],word,n+1);
        }
        return node;
    }

    bool get(Node *node, string word, int n){
        if(node == NULL){
            return false;
        }
        if(n == word.size()){
            return node->isEnd;
        }else{
            int pos = word[n] - 'a';
            return get(node->child[pos],word,n+1);
        }
    }

    bool find(Node *node, string word, int n){
        if(node == NULL){
            return false;
        }
        if(n == word.size()){
            return true;
        }else{
            int pos = word[n] - 'a';
            return find(node->child[pos],word,n+1);
        }
    }

    Node* del(Node *node, string word, int n){
        if(node == NULL){
            return NULL;
        }
        if(n == word.size()){
            node->isEnd = false;
        }else{
            int pos = word[n] - 'a';
            node->child[pos] = del(node->child[pos],word,n+1);
        }
        if(node->isEnd == true){
            return node;
        }
        for(int i=0;i<26;i++){
            if(node->child[i] != NULL){
                return node;
            }
        }
        delete node;
        return NULL;
    }
};

线段树

线段树是一个完全二叉树，它的基本含义是，用结点所在位置表示一个范围，二叉树的根结点位置表示从left到right的范围，结点的值代表这个范围之上的属性，如最大值。所以，这里的二叉树采用的是数组的形式实现。线段树适用的场景是，需要实时查询某个范围的值，并且需要更新某个值的场景。下面是具体的实现，结点表示某个范围的最大值。

/* 线段树数组一般是原数组的四倍 */
void buildTree(vector<int> &v, vector<int> &num, int pos, int left, int right){
    if(left == right){
        v[pos] = num[left];
        return;
    }
    int mid = (right + left) / 2;
    buildTree(v,num,pos*2+1,left,mid);
    buildTree(v,num,pos * 2 + 2,mid+1,right);
    v[pos] = max(v[pos * 2 +1],v[pos * 2 + 2]);
}

int searchTree(vector<int> &v,int pos, int left, int right, int qleft, int qright){
    if(qleft > right || qright < left){
        return 0;
    }
    if(qleft <= left && qright >= right){
        return v[pos];
    }
    int mid = (left + right) / 2;
    return max(searchTree(v,pos * 2 + 1,left,mid,qleft,qright),searchTree(v,pos*2+2,mid+1,right,qleft,qright));
}

void updateTree(vector<int> &v,int pos,int left,int right,int index,int value){
    if(index == left && index == right){
        v[pos] = value;
        return;
    }
    int mid = (right + left) / 2;
    if(index <= mid){
        updateTree(v,pos * 2 +1 ,left,mid,index,value);
    }else{
        updateTree(v,pos * 2 +2,mid+1,right,index,value);
    }
    v[pos] = max(v[pos*2+1],v[pos * 2 + 2]);
}