算法索引

学习相关算法时，使用的相关博文和模板的集合

线段树

线段树相关知识

模板

/**
 * @Description: 线段树（动态开点）
 * @Author: LFool
 * @Date 2022/6/7 09:15
 **/
public class SegmentTreeDynamic {
    class Node {
        Node left, right;
        int val, add;
    }
    private int N = (int) 1e9;
    private Node root = new Node();
    public void update(Node node, int start, int end, int l, int r, int val) {
        if (l <= start && end <= r) {
            node.val += (end - start + 1) * val;
            node.add += val;
            return ;
        }
        int mid = (start + end) >> 1;
        pushDown(node, mid - start + 1, end - mid);
        if (l <= mid) update(node.left, start, mid, l, r, val);
        if (r > mid) update(node.right, mid + 1, end, l, r, val);
        pushUp(node);
    }
    public int query(Node node, int start, int end, int l, int r) {
        if (l <= start && end <= r) return node.val;
        int mid = (start + end) >> 1, ans = 0;
        pushDown(node, mid - start + 1, end - mid);
        if (l <= mid) ans += query(node.left, start, mid, l, r);
        if (r > mid) ans += query(node.right, mid + 1, end, l, r);
        return ans;
    }
    private void pushUp(Node node) {
        node.val = node.left.val + node.right.val;
    }
    private void pushDown(Node node, int leftNum, int rightNum) {
        if (node.left == null) node.left = new Node();
        if (node.right == null) node.right = new Node();
        if (node.add == 0) return ;
        node.left.val += node.add * leftNum;
        node.right.val += node.add * rightNum;
        // 对区间进行「加减」的更新操作，下推懒惰标记时需要累加起来，不能直接覆盖
        node.left.add += node.add;
        node.right.add += node.add;
        node.add = 0;
    }
}


public void buildTree(Node node, int start, int end) {
    // 到达叶子节点
    if (start == end) {
        node.val = arr[start];
        return ;
    }
    int mid = (start + end) >> 1;
    buildTree(node.left, start, mid);
    buildTree(node.right, mid + 1, end);
    // 向上更新
    pushUp(node);
}
// 向上更新
private void pushUp(Node node) {
    node.val = node.left.val + node.right.val;
}

字典树

字典树相关知识
题目
模板

public class Trie {
        private TrieNode root;

        public Trie() {
            root = new TrieNode();
            root.wordEnd = false;
        }

        public void insert(String word) {
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) {
                Character c = new Character(word.charAt(i));
                if (!node.childdren.containsKey(c)) {
                    node.childdren.put(c, new TrieNode());
                }
                node = node.childdren.get(c);
            }
            node.wordEnd = true;
        }

        public boolean search(String word) {
            TrieNode node = root;
            boolean found = true;
            for (int i = 0; i < word.length(); i++) {
                Character c = new Character(word.charAt(i));
                if (!node.childdren.containsKey(c)) {
                    return false;
                }
                node = node.childdren.get(c);
            }
            return found && node.wordEnd;
        }

        public boolean startsWith(String prefix) {
            TrieNode node = root;
            boolean found = true;
            for (int i = 0; i < prefix.length(); i++) {
                Character c = new Character(prefix.charAt(i));
                if (!node.childdren.containsKey(c)) {
                    return false;
                }
                node = node.childdren.get(c);
            }
            return found;
        }

    }

    public class TrieNode {
        Map<Character, TrieNode> childdren;
        boolean wordEnd;

        public TrieNode() {
            childdren = new HashMap<Character, TrieNode>();
            wordEnd = false;
        }
    }

链式前向星

基础
例题
模板

public static class Edge{
    int to;
    int w;
    int next;
}
    
public static void add(int u,int v,int w){
    edges[cnt] = new Edge();//创建一条边将其放入边集数组
    edges[cnt].to = v;
    edges[cnt].w = w;
    edges[cnt].next = head[u];
    head[u] = cnt++;
}

十大排序算法

基础
题目
基数排序的妙用