夏天时光空间

Log

第 354 场周赛 全部AC了，但是前缀树好久没写花了很长时间，记录一下模板，以后直接copy，后序常见算法模板也会总结下。

前缀树算法模板

        static class Trie {
            private TrieNode root;

            /**
             * Initialize your data structure here.
             */
            public Trie() {
                root = new TrieNode();
            }

            /**
             * Inserts a word into the trie.
             */
            public void insert(String word) {
                TrieNode node = root;
                int n = word.length();
                for (int i = 0; i < n; i++) {
                    char ch = word.charAt(i);
                    TrieNode next = node.get(ch);
                    if (next == null) {
                        next = new TrieNode();
                        node.put(ch, next);
                    }
                    node = next;
                }
                node.setIsEnd();
            }

            public boolean search(String word) {
                TrieNode node = root;
                int n = word.length();
                for (int i = 0; i < n; i++) {
                    char ch = word.charAt(i);
                    TrieNode next = node.get(ch);
                    if ( next== null) {
                        return false;
                    }
                    node = next;
                }
                return node.isEnd;
            }


            public int contains(String word) {
                int n = word.length();
                TrieNode node = root;
                for (int i = 0; i < n; i++) {
                    char ch = word.charAt(i);
                    TrieNode next = node.get(ch);
                    if (next == null) {
                        return -1;
                    }
                    if (next.isEnd) {
                        return i + 1;
                    }
                    node = next;
                }
                return -1;
            }
        }

        static class TrieNode {
            private TrieNode[] links;

            private final int R = 26;

            private boolean isEnd;

            public TrieNode() {
                links = new TrieNode[R];
            }

            public boolean containsKey(char ch) {
                return links[ch - 'a'] != null;
            }

            public TrieNode get(char ch) {
                return links[ch - 'a'];
            }

            public void put(char ch, TrieNode node) {
                links[ch - 'a'] = node;
            }

            public boolean isEnd() {
                return isEnd;
            }

            public void setIsEnd() {
                this.isEnd = true;
            }
        }

线段树算法模板

        class SegmentTree {
            int[] tree;
            int[] nums;

            public SegmentTree(int[] nums) {
                this.nums = nums;
                int n = nums.length;
                int height = (int) Math.ceil(Math.log(n) / Math.log(2));
                int maxSize = 2 * (int) Math.pow(2, height) - 1;
                tree = new int[maxSize];
                buildTree(0, 0, n - 1);
            }

            private int buildTree(int node, int start, int end) {
                if (start == end) {
                    tree[node] = nums[start];
                    return tree[node];
                }

                int mid = start + (end - start) / 2;
                tree[node] = buildTree(2 * node + 1, start, mid) +
                        buildTree(2 * node + 2, mid + 1, end);
                return tree[node];
            }

            public int query(int queryStart, int queryEnd) {
                return queryHelper(0, 0, nums.length - 1, queryStart, queryEnd);
            }

            private int queryHelper(int node, int start, int end, int queryStart, int queryEnd) {
                if (queryStart <= start && queryEnd >= end) {
                    return tree[node];
                }

                if (queryStart > end || queryEnd < start) {
                    return 0;
                }

                int mid = start + (end - start) / 2;
                return queryHelper(2 * node + 1, start, mid, queryStart, queryEnd) +
                        queryHelper(2 * node + 2, mid + 1, end, queryStart, queryEnd);
            }

            public void update(int index, int newValue) {
                int diff = newValue - nums[index];
                nums[index] = newValue;
                updateHelper(0, 0, nums.length - 1, index, diff);
            }

            private void updateHelper(int node, int start, int end, int index, int diff) {
                if (index < start || index > end) {
                    return;
                }

                tree[node] += diff;

                if (start != end) {
                    int mid = start + (end - start) / 2;
                    updateHelper(2 * node + 1, start, mid, index, diff);
                    updateHelper(2 * node + 2, mid + 1, end, index, diff);
                }
            }
        }