线段树

三个主要方法的模板

import java.util.*;
public class Main {
    // main
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tree[] = new int[1000];
        int arr[] = { 0, 1, 3, 5, 7, 9, 11 };
        // for (int i = 1; i < length; i++) { //存储数据
        // arr[i] = sc.nextInt();
        // }
        create_tree(arr, tree, 0, 1, arr.length - 1); // 这里记得减1 因为arr[]是从0开始存储数据
        for (int i = 0; i < tree.length; i++) {
            System.out.print(tree[i] + " ");
        }
        System.out.println();
        update(arr, tree, 0, 1, arr.length - 1, 5, 6);
        for (int i = 0; i < tree.length; i++) {
            System.out.print(tree[i] + " ");
        }System.out.println();
        System.out.println(querey(tree, arr, 0, 1, 6, 2, 5));

    }
    // create
    public static void create_tree(int arr[], int tree[], int node, int start, int end) { // create建树方法！！！
        if (start == end) { // 离散化的点进行调整！！！
            tree[node] = arr[start];
        } else {
            int left_node = 2 * node + 1; // 0 | 1 2 | 3 4 5 6 ...........
            int right_node = 2 * node + 2;
            int mid = (start + end) / 2;
            create_tree(arr, tree, left_node, start, mid);
            create_tree(arr, tree, right_node, mid + 1, end);
            tree[node] = tree[left_node] + tree[right_node]; // 核心代码
        }
    }
    // update
    public static void update(int arr[], int tree[], int node, int start, int end, int idx, int val) {
        if (start == end) {
            arr[start] = val;
            tree[node] = val;
        } else {
            int left_node = 2 * node + 1; // 0 | 1 2 | 3 4 5 6 ...........
            int right_node = 2 * node + 2;
            int mid = (start + end) / 2;
            if (idx = start) {
                update(arr, tree, left_node, start, mid, idx, val);
            } else if (idx = mid + 1) {
                update(arr, tree, right_node, mid + 1, end, idx, val);
            }
            tree[node] = tree[left_node] + tree[right_node]; // 核心代码
        }
    }
    // querey
    public static int querey(int tree[], int arr[], int node, int start, int end, int L, int R) {
        if (R < start || end < L) { // 排除范围之外
            return 0;
        } else if (L <= start && end <= R)
            return tree[node];
        else if (start == end)
            return node;
        else {
            int mid = (start + end) / 2;
            int left_node = node * 2 + 1;
            int right_node = node * 2 + 2;
            int sum_left = querey(tree, arr, left_node, start, mid, L, R);
            int sum_right = querey(tree, arr, right_node, mid + 1, end, L, R);
            return sum_left + sum_right;
        }
    }
}