eleven26

public class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }

    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }
}

construct(arr):
    // n 是子结点所在那一层的节点个数
    n = length(arr)
    // 开 2 * n 的数组，这样就可以一半用来存储子结点（叶子结点存储的是一个数组成的区间），一半用来存储非叶子结点（非叶子结点存储的是区间汇总信息）
    segmentTree = new int[2 * n]
    // 先初始化的是叶子结点，叶子结点的范围是 [n, 2 * n - 1]
    for i from n to 2 * n - 1:
        segmentTree[i] = arr[i - n]
    // 初始化父结点，就是合并区间的操作，通过左右叶子结点得到区间汇总信息
    for i from n - 1 to 1:
        segmentTree[i] = merge(segmentTree[2 * i], segmentTree[2 * i + 1])

segmentTree[1] = arr[0:8)
segmentTree[2] = arr[0:4)
segmentTree[3] = arr[4:8)
segmentTree[4] = arr[0:2)
segmentTree[5] = arr[2:4)
segmentTree[6] = arr[4:6)
segmentTree[7] = arr[6:8)
segmentTree[8] = arr[0]
segmentTree[9] = arr[1]
segmentTree[10] = arr[2]
segmentTree[11] = arr[3]
segmentTree[12] = arr[4]
segmentTree[13] = arr[5]
segmentTree[14] = arr[6]
segmentTree[15] = arr[7]

update(i, value):
    // 原数组在线段树里面的存储位置是从下标 n 开始的
    i = i + n;
    // 更新原数组的值
    segmentTree[i] = value;
    while (i > 1):
        // 向上更新关联的父结点，直到根结点。i / 2 是 i 的父结点在线段树中的下标。
        i = i / 2;
        // 如果父结点在线段树的下标为 i，那么左孩子在线段树的下标为 2 * i，右孩子在线段树的下标为 2 * i + 1
        segmentTree[i] = merge(segmentTree[2 * i], segmentTree[2 * i + 1])

minimum(left, right):
    // left 在线段树中的下标位置
    left = left + n
    // right 在线段树中的下标位置
    right = right + n
    // 初始化最小值
    minimum = Integer.MAX_VALUE
    while left < right:
        if left is odd:
            // left is out of range of parent interval, check value of left node first, then shift it right in the same level
            minimum = min(minimum, segmentTree[left])
            left = left + 1
        if right is odd:
            // right is out of range of current interval, shift it left in the same level and then check the value
            right = right - 1
            minimum = min(minimum, segmentTree[right])
        
        // 向根结点遍历
        left = left / 2
        right = right / 2

package com.baiguiren.leetcode;

import java.util.ArrayList;

public class MinSegmentTree {
    public static void main(String[] args) {
        MinSegmentTree tree = new MinSegmentTree(new int[]{1, 5, 3, 7, 3, 6, 5, 7});
        int min = tree.minimum(1, 2);
        System.out.println("min=" + min);
    }

    private ArrayList<Integer> minSegmentTree;
    private int n;

    public MinSegmentTree(int[] arr) {
        n = arr.length;
        minSegmentTree = new ArrayList<>(2 * n);

        for (int i = 0; i < n; i++) {
            minSegmentTree.add(0);
        }

        for (int i = n; i < 2 * n; i++) {
            minSegmentTree.add(arr[i - n]);
        }

        for (int i = n - 1; i > 0; i--) {
            minSegmentTree.set(i, Math.min(minSegmentTree.get(2 * i), minSegmentTree.get(2 * i + 1)));
        }
    }

    public void update(int i, int value) {
        i = i + n;
        minSegmentTree.set(i, value);

        while (i > 1) {
            i = i / 2;
            minSegmentTree.set(i, Math.min(minSegmentTree.get(2 * i), minSegmentTree.get(2 * i + 1)));
        }
    }

    public int minimum(int left, int right) {
        left = left + n;
        right = right + n;
        int min = Integer.MAX_VALUE;

        // 如果 left == right 说明，最小值已经产生，只可能是下一层的数
        // left == right 说明缩减到只有一个数字的区间了。
        while (left < right) {
            if ((left & 1) == 1) {
                min = Math.min(min, minSegmentTree.get(left));
                left = left + 1;
            }

            if ((right & 1) == 1) {
                right--;
                min = Math.min(min, minSegmentTree.get(right));
            }

            left >>= 1;
            right >>= 1;
        }

        return min;
    }
}

public class SumSegmentTree {
    public static void main(String[] args) {
        SumSegmentTree tree = new SumSegmentTree(new int[]{1, 5, 3, 7, 3, 6, 5, 7});
        int sum = tree.sum(1, 3);
        System.out.println("sum=" + sum);
    }

    private final ArrayList<Integer> sumSegmentTree;
    private final int n;

    public SumSegmentTree(int[] arr) {
        n = arr.length;
        sumSegmentTree = new ArrayList<>(2 * n);

        for (int i = 0; i < n; i++) {
            sumSegmentTree.add(0);
        }

        for (int i = n; i < 2 * n; i++) {
            sumSegmentTree.add(arr[i - n]);
        }

        for (int i = n - 1; i > 0; i--) {
            sumSegmentTree.set(i, sumSegmentTree.get(2 * i) + sumSegmentTree.get(2 * i + 1));
        }
    }

    public void update(int i, int value) {
        i = i + n;
        sumSegmentTree.set(i, value);

        while (i > 1) {
            i = i / 2;
            sumSegmentTree.set(i, sumSegmentTree.get(2 * i) +sumSegmentTree.get(2 * i + 1));
        }
    }

    public int sum(int left, int right) {
        left = left + n;
        right = right + n;
        int sum = 0;

        while (left < right) {
            if ((left & 1) == 1) {
                sum += sumSegmentTree.get(left);
                left = left + 1;
            }

            if ((right & 1) == 1) {
                right--;
                sum += sumSegmentTree.get(right);
            }

            left >>= 1;
            right >>= 1;
        }

        return sum;
    }
}