今天寫了一些題目，做的全是線段樹的題。但我打算明天復習樹狀數(shù)組力惯，對可以用好多種做法做的題目打算按照線段樹寫一遍，再用樹狀數(shù)組寫一遍召嘶。

基本上來說線段樹是來做區(qū)間修改和查詢的父晶。在有修改的情況下，動態(tài)查詢一個區(qū)間內(nèi)的最大值弄跌、最小值或者和一類的指標甲喝，這種情況下我們可以用線段樹。比方說一個求區(qū)間和的線段樹碟绑，我們會定義一個類俺猿，叫SegmentTreeNode茎匠，然后有三個方法，buildTree押袍、updateTree和querySum诵冒。代碼模板如下：

class SegmentTreeNode {
    public int start, end, sum;
    public SegmentTreeNode left, right;
    
    public SegmentTreeNode(int start, int end, int sum, SegmentTreeNode left, SegmentTreeNode right) {
        this.start = start;
        this.end = end;
        this.sum = sum;
        this.left = left;
        this.right = right;
    }
}

    private SegmentTreeNode buildTree(int start, int end, int[] nums) {
        if (start == end) {
            return new SegmentTreeNode(start, end, nums[start], null, null);
        }
        
        int mid = start + (end - start) / 2;
        SegmentTreeNode left = buildTree(start, mid, nums);
        SegmentTreeNode right = buildTree(mid + 1, end, nums);
        
        return new SegmentTreeNode(start, end, left.sum + right.sum, left, right);
    }
    
    private void updateTree(SegmentTreeNode root, int index, int val) {
        if (root.start == index && root.end == index) {
            root.sum = val;
            return;
        }
        
        int mid = root.start + (root.end - root.start) / 2;
        if (index <= mid) {
            updateTree(root.left, index, val);
        }
        else {
            updateTree(root.right, index, val);
        }
        
        root.sum = root.left.sum + root.right.sum;
    }
    
    private int querySum(SegmentTreeNode root, int i, int j) {
        if (root.start == i && root.end == j) {
            return root.sum;
        }
        
        int mid = root.start + (root.end - root.start) / 2;
        if (j <= mid) {
            return querySum(root.left, i, j);
        }
        else if (i > mid) {
            return querySum(root.right, i, j);
        }
        
        return querySum(root.left, i, mid) + querySum(root.right, mid + 1, j);
    }

從上述模板我們也可以看出一些線段樹的使用場景。比方說buildTree谊惭，是一次性建完這棵樹的汽馋，后面或許對于樹上節(jié)點的值進行修改，但樹的結(jié)構(gòu)從建出來之后就再也沒有改過圈盔。也就是說如果在某道題中豹芯，你需要動態(tài)增刪樹的一些節(jié)點，那應該是不能用線段樹驱敲。
在很多時候铁蹈，如果跟區(qū)間修改查詢相關(guān)，可以往這個方向想众眨。如果這樣的話最需要考慮的東西就是“以什么建樹”和“樹上攜帶什么信息”握牧。當然上面這個題目是以輸入數(shù)組建樹的，但實質(zhì)上應該去思考當你要做區(qū)間查詢的時候娩梨，所謂區(qū)間的每個點代表什么沿腰。上面這個題目是以下標為查詢的key的，所以樹也是按照下標來做查詢的狈定。那么如果有些題目要查詢某個范圍內(nèi)的值颂龙，那就要用“值”來建樹。