线段树

说明：

线段树模板

推荐视屏：

【喵的算法课】线段树 数据结构【6期】_哔哩哔哩_bilibili

推荐文章：

《算法竞赛》上册 罗勇军 第175页

Java代码模板：

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177

import java.util.Scanner;

/**
 * @author 长白崎
 * @version 1.0
 * @description: 线段树
 * 这个模板主要展示了基本的构建，以及一些基本的使用，详细的使用需要通过题目要求动态修改。
 * @date 2023/5/2 1:54
 */
public class SegmentTree {


    public static void main(String[] args) {

        //测试数据
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入数组长度：");
        int n = sc.nextInt();
        int data[] = new int[n + 1]; //用于寄存值的数组
        int tree[] = new int[(n + 1) * 4]; //线段树的数组
        int lazyTag[] = new int[(n + 1) * 4]; //懒标记数组
        //寄存数组的值输入
        System.out.println("请输入数组内的值：");
        for (int i = 1; i <= n; ++i) {
            data[i] = sc.nextInt();
        }
        //构建线段树
        build(tree, data, 1, 1, n);

        //通过线段树查询区间总和
        System.out.println("请输入需要查询的区间：");
        int start = sc.nextInt();
        int end = sc.nextInt();
        System.out.println(query(tree, lazyTag, start, end, 1, 1, n));

        //更新线段树
        System.out.println("请输入需要更新的区间以及更新的值为多少：");
        start = sc.nextInt();
        end = sc.nextInt();
        int v = sc.nextInt();
        update(tree,lazyTag,start,end,1,n,1,v);

        //通过线段树查询区间总和
        System.out.println("请输入需要查询的区间：");
        start = sc.nextInt();
        end = sc.nextInt();
        System.out.println(query(tree, lazyTag, start, end, 1, 1, n));

    }

    /**
     * 获取当前节点编号的左儿子结点编号
     *
     * @param p 代表当前结点的标签序号
     * @return 返回其左子节点的标签号
     */
    public static int ls(int p) {
        return p << 1;
    }

    /**
     * 获取当前结点编号的右儿子结点编号
     *
     * @param p 代表当前结点的标签序号
     * @return 代表其右子结点的标签号
     */
    public static int rs(int p) {
        return p << 1 | 1;
    }

    /**
     * 用于计算当前结点所对应的左右子结点的总和
     *
     * @param tree 所构建的线段树
     * @param p    表示我们需要计算的结点的标签
     */
    public static void pushUp(int tree[], int p) {
        tree[p] = tree[ls(p)] + tree[rs(p)]; //区间和
    }

    /**
     * 构建线段树
     *
     * @param tree
     * @param left
     * @param right
     */
    public static void build(int tree[], int data[], int p, int left, int right) {
        if (left == right) {
            tree[p] = data[left];
            return;
        }

        int mid = (left + right) >> 1;
        build(tree, data, ls(p), left, mid);
        build(tree, data, rs(p), mid + 1, right);
        pushUp(tree, p);
    }

    /**
     * 区间和查询
     *
     * @param tree 构建的线段树
     * @param L    代表我们需要查询的数组对应的区间左标
     * @param R    代表我们需要查询的数组对应的区间右标
     * @param p    代表的是我们当前的所查询基于的父节点的结点标签
     * @param ls   代表当前父结点的范围左标
     * @param rs   代表当前父结点的范围右标
     * @return 返回最终的区间总和值
     */
    public static int query(int tree[], int lazyTag[], int L, int R, int p, int ls, int rs) {
        //完全覆盖
        if (L <= ls && R >= rs) return tree[p];
        pushDown(tree, lazyTag, ls, rs, p);
        int res = 0;
        int mid = (ls + rs) >> 1;
        if (L <= mid) res += query(tree, lazyTag, L, R, ls(p), ls, mid);
        if (R > mid) res += query(tree, lazyTag, L, R, rs(p), mid + 1, rs);
        return res;
    }

    /**
     * 懒标记更新函数
     *
     * @param tree    线段树的数组
     * @param lazyTag 懒标记数组
     * @param ls      需要修改的区域的左边界
     * @param rs      需要修改区域的右边界
     * @param p       当前修改区域结点的标签序号
     * @param v       需要修改的值
     */
    public static void addTag(int tree[], int lazyTag[], int ls, int rs, int p, int v) {
        lazyTag[p] += v;
        tree[p] += v * (rs - ls + 1);
    }

    /**
     * 懒标记向下传递
     *
     * @param tree    线段树的数组
     * @param lazyTag 懒标记数组
     * @param ls      区间的左边界
     * @param rs      区间的右边界
     * @param p       对应区间的标签
     */
    public static void pushDown(int tree[], int lazyTag[], int ls, int rs, int p) {
        //拦截不需要向下传递的懒标记
        if (lazyTag[p] == 0)
            return;

        //开始懒标记传递
        int mid = (ls + rs) >> 1;
        addTag(tree, lazyTag, ls, mid, ls(p), lazyTag[p]);
        addTag(tree, lazyTag, mid + 1, rs, rs(p), lazyTag[p]);
        lazyTag[p] = 0;
    }

    public static void update(int tree[], int lazyTag[], int L, int R, int ls, int rs, int p, int v) {
        if (L <= ls && R >= rs) {
            addTag(tree, lazyTag, ls, rs, p, v);
            return;
        }
        //向下传递
        pushDown(tree,lazyTag,ls,rs,p);
        int mid = (ls+rs)>>1;
        //如果左子结点符合要求那么递归进左子结点继续
        if (L<=mid) update(tree,lazyTag,L,R,ls,mid,ls(p),v);
        //如果右子结点符合要求那么递归进右子结点继续
        if(R > mid) update(tree,lazyTag,L,R,mid+1,rs,rs(p),v);
        //更新当前结点的值
        pushUp(tree,p);
    }


}