JAVA版线段树(单修&区修)

单修：

import java.util.Scanner;
public class Main {
    static class node{
        int l, r;
        long ans;
        int mid() {
            return (l + r) >> 1;
        }
    }
    static final int maxn = 100005;
    static node[] tree = new node[maxn << 2];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        Build(1, 1, n);
        while(m-- != 0) {
            int k = scanner.nextInt();
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            if(k != 0) System.out.println(Query(1, l, r));
            else UpDate(1, l, r);
        }
        scanner.close();
    }
    public static void Build(int root, int l, int r) {
        tree[root] = new node();
        tree[root].l = l;
        tree[root].r = r;
        if(l == r) return;
        int mid = tree[root].mid();
        Build(root << 1, l, mid);
        Build(root << 1 | 1, mid + 1, r);
    }
    public static void UpDate(int root, int vis, int pos) {
        if(tree[root].l == tree[root].r){
            tree[root].ans += pos;
            return;
        }
        int mid = tree[root].mid();
        if(vis <= mid) UpDate(root << 1, vis, pos);
        else UpDate(root << 1 | 1, vis, pos);
        tree[root].ans = tree[root << 1].ans + tree[root << 1 | 1].ans;
    }
    public static long Query(int root, int l, int r) {
        if(tree[root].l >= l && tree[root].r <= r) return tree[root].ans;
        int mid = tree[root].mid();
        if(r <= mid) return Query(root << 1, l, r);
        else if(l > mid) return Query(root << 1 | 1, l, r);
        else return Query(root << 1, l, mid) + Query(root << 1 | 1, mid + 1, r);
    }
}

区修：

import java.util.Scanner;
public class Main {
    static class node{
        int l, r;
        long ans, lazy;
        int mid() {
            return (l + r) >> 1;
        }
    }
    static final int maxn = 100005;
    static int[] arr = new int[maxn];
    static node[] tree = new node[maxn << 2];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        for(int i = 1; i <= n; i++) arr[i] = scanner.nextInt();
        Build(1, 1, n);
        String s;
        int x, y, z;
        while(m-- != 0){
            s = scanner.next();
            if(s.charAt(0) == 'C'){
                x = scanner.nextInt();
                y = scanner.nextInt();
                z = scanner.nextInt();
                UpDate(1, x, y, z);
            }
            else{
                x = scanner.nextInt();
                y = scanner.nextInt();
                System.out.println(Query(1, x, y));
            }
        }
        scanner.close();
    }
    public static void PushDown(int root, int m){
        if(tree[root].lazy != 0){
            tree[root << 1].lazy += tree[root].lazy;
            tree[root << 1 | 1].lazy += tree[root].lazy;
            tree[root << 1].ans += tree[root].lazy * (m - (m >> 1));
            tree[root << 1 | 1].ans += tree[root].lazy * (m >> 1);
            tree[root].lazy = 0;
        }
    }
    public static void Build(int root, int l, int r) {
        tree[root] = new node();
        tree[root].l = l;
        tree[root].r = r;
        tree[root].lazy = 0;
        if(tree[root].l == tree[root].r){
            tree[root].ans = arr[l];
            return;
        }
        int mid = tree[root].mid();
        Build(root << 1, l, mid);
        Build(root << 1 | 1, mid + 1, r);
        tree[root].ans = tree[root << 1].ans + tree[root << 1 | 1].ans;
    }
    public static void UpDate(int root, int l, int r, int c) {
        if(tree[root].l == l && tree[root].r == r){
            tree[root].lazy += c;
            tree[root].ans += c * (r - l + 1);
            return;
        }
        if(tree[root].l == tree[root].r) return;
        PushDown(root, tree[root].r - tree[root].l + 1);
        int mid = tree[root].mid();
        if(r <= mid) UpDate(root << 1, l, r, c);
        else if(l > mid) UpDate(root << 1 | 1, l, r, c);
        else{
            UpDate(root << 1, l, mid, c);
            UpDate(root << 1 | 1, mid + 1, r, c);
        }
        tree[root].ans = tree[root << 1].ans + tree[root << 1 | 1].ans;
    }
    public static long Query(int root, int l, int r) {
        if(tree[root].l >=l && tree[root].r <= r) return tree[root].ans;
        PushDown(root, tree[root].r - tree[root].l + 1);
        int mid = tree[root].mid();
        if(r <= mid) return Query(root << 1, l, r);
        else if(l > mid) return Query(root << 1 | 1, l, r);
        else return Query(root << 1, l, mid) + Query(root << 1 | 1, mid + 1, r);
    }
}