算法学习-线段树模板（JAVA实现）

本文最后更新于：March 18, 2022 pm

纸上得来终觉浅，绝知此事要躬行。路漫漫其修远兮，吾将上下而求索！知识是经过历史的巨人沉淀下来的，别总想着自己能够快速学会，多花点时间去看看，也许会发现些不同的东西。你能快速学会的、觉得简单的东西，对于别人来说也是一样的。人外有人，天外有天。当努力到达了一定的程度，幸运自会与你不期而遇。

目录

单点修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import java.io.*;
import java.math.BigInteger;
import java.util.Scanner;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 100000+7;

    public static int[] a = new int[maxd]; //原数组
    public static int[] tree = new int[maxd*4]; //树存储

    //初始化建树
    public static void build(int p,int l,int r){
        if(l==r){
            tree[p]=a[l];
            return ;
        }
        int mid = (r+l)/2; // 防止爆范围
        build(p*2,l,mid); //左子树
        build(p*2+1,mid+1,r); //右子树
        tree[p]=tree[p*2]+tree[p*2+1];
    }

    //将x位置的值加上num
    public static void update(int p,int l,int r,int x,int num){
        if(x>r||x<l) return ;
        if(l==r&&l==x){ //找到x位置
            tree[p] += num; //灵活变
            return ;
        }
        int mid = (r+l)/2;
        update(p*2,l,mid,x,num);
        update(p*2+1,mid+1,r,x,num);
        tree[p]=tree[p*2]+tree[p*2+1];
    }

    //查询区间和
    public static int query(int p,int l, int r ,int x, int y){
        if(x<=l&&r<=y) return tree[p];
        if(x>r||y<l) return 0;
        int mid = (r+l)/2;
        int sum = 0;
        sum+=query(p*2,l,mid,x,y);
        sum+=query(p*2+1,mid+1,r,x,y);
        return sum;
    }


    public static void main(String[] args) throws Exception {

        int n = nextInt();
        int m = nextInt();
        for(int i=1;i<=n;++i){
            a[i] = nextInt();
        }
        build(1,1,n); //注意此位置必须在a数组输入后
        for(int i=1;i<=m;++i){
            int a1 = nextInt();
            int a2 = nextInt();
            int a3 = nextInt();
            if(a1==1) update(1,1,n,a2,a3);
            else System.out.println(query(1,1,n,a2,a3));
        }

        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers(); //可单独使用来还原数字
    }

    public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }

}

测试数据：

1
2
3
4
10 2
1 2 3 4 5 6 7 8 9 10
1 1 9
2 1 10

结果

1
64

区间修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
import java.io.*;
import java.math.BigInteger;
import java.util.Scanner;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 100000+7;

    public static int[] a = new int[maxd]; //原数组
    public static int[] tree = new int[maxd*4]; //树存储
    public static int[] lazy = new int[maxd*4]; //懒惰标记

    //初始化建树
    public static void build(int p,int l,int r){
        if(l==r){
            tree[p]=a[l];
            return ;
        }
        int mid = (r+l)/2; // 防止爆范围
        build(p*2,l,mid); //左子树
        build(p*2+1,mid+1,r); //右子树
        tree[p]=tree[p*2]+tree[p*2+1];
        lazy[p]=0;
    }
    public static void push_down(int p ,int l ,int r ){
        if(lazy[p]!=0){
            lazy[p*2] += lazy[p];
            lazy[p*2+1] += lazy[p];
            int mid = (r+l)/2;
            tree[p*2] += (mid-l+1) * lazy[p];
            tree[p*2+1] += (r-mid) * lazy[p];
            lazy[p]=0;
        }

    }

    //将区间（x,y）的值加上num
    public static void update(int p,int l,int r,int x,int y,int num){
        if(x>r||y<l) return ;
        if(x<=l&&r<=y){ //找到区间
            lazy[p] += num;
            tree[p] += (r-l+1)*num;
            return ;
        }
        push_down(p,l,r);
        int mid = (r+l)/2;
        update(p*2,l,mid,x,y,num);
        update(p*2+1,mid+1,r,x,y,num);
        tree[p]=tree[p*2]+tree[p*2+1];
    }

    //查询区间和
    public static int query(int p,int l, int r ,int x, int y){
        if(x<=l&&r<=y) return tree[p];
        if(x>r||y<l) return 0;
        push_down(p,l,r);
        int mid = (r+l)/2;
        int sum = 0;
        sum+=query(p*2,l,mid,x,y);
        sum+=query(p*2+1,mid+1,r,x,y);
//        tree[p]=tree[p*2]+tree[p*2+1];
        return sum;
    }


    public static void main(String[] args) throws Exception {

        int n = nextInt();
        int m = nextInt();
        for(int i=1;i<=n;++i) a[i] = nextInt();
        build(1,1,n);
        for(int i=1;i<=m;++i){
            int a1 = nextInt();
            if(a1==1) {
                int a2 = nextInt();
                int a3 = nextInt();
                System.out.println(query(1,1,n,a2,a3));
            }
            else {
                int a2 = nextInt();
                int a3 = nextInt();
                int a4 = nextInt();
                update(1,1,n,a2,a3,a4);
            }
        }

        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers(); //可单独使用来还原数字
    }

    public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }

}

测试数据：

1
2
3
4
5
5 3
1 2 3 4 5
1 1 5
2 1 5 -1
1 1 5

输出：

1
2
15
10

还有二维线段树。有机会再写吧。