热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

线段树详解与实现

本文详细介绍了线段树的基本概念及其在编程竞赛中的应用,并提供了一个具体的线段树实现代码示例。

线段树是一种高效的数据结构,常用于解决区间查询和更新问题。它通过将区间分割成多个子区间来提高查询效率,特别适用于需要频繁进行区间修改和查询的场景。

1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7
8 const int MAXN = 200005;
9
10 int n, m, op, a, b;
11 long long val;
12 int arr[MAXN];
13
14 struct SegmentTree {
15 int left, right;
16 long long sum;
17 int lazy;
18 } tree[4 * MAXN];
19
20 void pushUp(int node) {
21 tree[node].sum = tree[node * 2].sum + tree[node * 2 + 1].sum;
22 }
23
24 void pushDown(int node) {
25 if (tree[node].lazy) {
26 tree[node * 2].lazy += tree[node].lazy;
27 tree[node * 2 + 1].lazy += tree[node].lazy;
28 tree[node * 2].sum += (tree[node * 2].right - tree[node * 2].left + 1) * tree[node].lazy;
29 tree[node * 2 + 1].sum += (tree[node * 2 + 1].right - tree[node * 2 + 1].left + 1) * tree[node].lazy;
30 tree[node].lazy = 0;
31 }
32 }
33
34 void build(int node, int start, int end) {
35 tree[node].left = start;
36 tree[node].right = end;
37 tree[node].lazy = 0;
38 if (start == end) {
39 tree[node].sum = arr[start];
40 return;
41 }
42 int mid = (start + end) / 2;
43 build(node * 2, start, mid);
44 build(node * 2 + 1, mid + 1, end);
45 pushUp(node);
46 }
47
48 void update(int node, int start, int end, long long value) {
49 if (tree[node].left >= start && tree[node].right <= end) {
50 tree[node].lazy += value;
51 tree[node].sum += (tree[node].right - tree[node].left + 1) * value;
52 return;
53 }
54 pushDown(node);
55 int mid = (tree[node].left + tree[node].right) / 2;
56 if (start <= mid) update(node * 2, start, end, value);
57 if (end > mid) update(node * 2 + 1, start, end, value);
58 pushUp(node);
59 }
60
61 long long query(int node, int start, int end) {
62 if (tree[node].left >= start && tree[node].right <= end) return tree[node].sum;
63 pushDown(node);
64 int mid = (tree[node].left + tree[node].right) / 2;
65 long long result = 0;
66 if (start <= mid) result += query(node * 2, start, end);
67 if (end > mid) result += query(node * 2 + 1, start, end);
68 return result;
69 }
70
71 int main() {
72 cin >> n;
73 for (int i = 1; i <= n; i++) cin >> arr[i];
74 build(1, 1, n);
75 cin >> m;
76 for (int i = 1; i <= m; i++) {
77 cin >> op;
78 if (op == 1) {
79 cin >> a >> b >> val;
80 update(1, a, b, val);
81 } else if (op == 2) {
82 cin >> a >> b;
83 cout <84 }
85 }
86 return 0;
87 }

查看代码

 


来源链接: https://www.cnblogs.com/chezhongyang/p/11584976.html


推荐阅读
author-avatar
不言不语都可以温柔_631
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有