java线段树模板

import java.util.*;

class Node{
    int l,r;               //区间边界
    int sum,lazyTag;       //区间和,lazy标记
    public Node(int l,int r){
        this.l=l;
        this.r=r;
    }
}

public class segmentTree{
    static Node[] tree = new Node[20];
    static int[] arr = {1,3,5,7,9};
    public static void main(String[] args) {
        segmentTree.create(0,0,4);
        segmentTree.update(0,1,3,1);
        System.out.println(segmentTree.query(0,0,3));
    }
    public static void create(int node, int l, int r) {
        tree[node] = new Node(l,r);
        if (l == r) {                   //到叶子节点
            tree[node].sum = arr[l];
            return;
        }
        else {
            int mid = (l + r) >> 1;
            int left_node = (node << 1) + 1;
            int right_node = (node << 1) + 2;
            create(left_node, l, mid);
            create(right_node, mid + 1, r);
            tree[node].sum = tree[left_node].sum + tree[right_node].sum;
        }
    }

    public static void update(int node,int l, int r,int val) {
        if(tree[node].l > r || tree[node].r < l) {                                                       //不在需要修改的区间里
            return;
        }else if (tree[node].l >= l && tree[node].r <= r) {                //完全包含于要求修改的区间
            tree[node].sum += (tree[node].r-tree[node].l+1)*val;
            tree[node].lazyTag+=val;
            return;
        } else {                              //不完全包含,需要向下查
            if(tree[node].lazyTag!=0)
                pushDowm(node);                      //懒标记下放
            int left_node = (node<<1)+1;
            int right_node = (node<<1)+2;
            update(left_node,l,r,val);
            update(right_node,l,r,val);
            tree[node].sum = tree[left_node].sum + tree[right_node].sum;         //更新完将数据传回给父节点
        }
    }

    public static void pushDowm(int node) {
        int left_node = (node<<1)+1;
        int right_node = (node<<1)+2;
        int val =tree[node].lazyTag;
        tree[left_node].sum += (tree[left_node].r - tree[left_node].l + 1) * val;
        tree[right_node].sum += (tree[right_node].r - tree[right_node].l + 1) * val;
        tree[left_node].lazyTag += val;
        tree[right_node].lazyTag += val;
        tree[node].lazyTag = 0;
    }

    public static int query(int node,int l,int r) {
        if (tree[node].l > r || tree[node].r < l) {
            return 0;
        }
        else if (tree[node].l >= l && tree[node].r <= r) {
            return tree[node].sum;
        }
        else {
            if(tree[node].lazyTag != 0)
                pushDowm(node);
            int mid = (l + r) / 2;
            int left_node = (node << 1) + 1;
            int right_node = (node << 1) + 2;
            return query(left_node, l, r) + query(right_node, l, r);
        }
    }
}