操作格子——线段树_第一行2个整数n,m。 接下来一行n个整数表示n个格子的初始权值。 接下来m行,每行3

问题描述
有n个格子，从左到右放成一排，编号为1-n。
共有m次操作，有3种操作类型：
1.修改一个格子的权值，
2.求连续一段格子权值和，
3.求连续一段格子的最大值。
对于每个2、3操作输出你所求出的结果。
输入格式
第一行2个整数n，m。
接下来一行n个整数表示n个格子的初始权值。
接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间[x,y]内格子权值和，p=3时表示求区间[x,y]内格子最大的权值。
输出格式
有若干行，行数等于p=2或3的操作总数。
每行1个整数，对应了每个p=2或3操作的结果。
样例输入
4 3
1 2 3 4
2 1 3
1 4 3
3 1 4
样例输出
6
3
数据规模与约定
对于20%的数据n <= 100，m <= 200。
对于50%的数据n <= 5000，m <= 5000。
对于100%的数据1 <= n <= 100000，m <= 100000，0 <= 格子权值 <= 10000。

解题过程：刚开始不懂线段树，用了两种不同的方法去解这道题，不过一种超时，一种超内存…但是这个过程还是挺不错，因为我的第二种方法在没有了解过线段树的基础下用到了类似线段树的数据结构。第一种方法是先对数据排序，从大到小，然后用散列表记录位置信息，接下来要解决的就是操作1跟3的处理了，操作1主要就是要维护有序数组和散列表，跟平时做维持一个有序数组的过程是类似的，只是多了需要根据新位置更新散列表的值而已；
操作3，我用两种方法来查找，第一种就是从有序数组第一个位置开始往后找，找到第一个属于指定区间的值，那么该值就是要找的值；第二种方法，因为有散列表，可以根据数据的原先编号找到该数据在有序数组中的位置，所以就是遍历指定区间中的所有元素，返回最大值。如何选择哪种方法呢？我是根据给定区间的大小来进行选择的，因为是错位方法（解决不了大数据）所以就不赘述了，其实想想也知道哪一种都需要耗费挺多时间…
第二种解决方案就是采用了空间换时间的思想，我会记录下所有可能的区间情况所对应的最大值，就是用二维数组(themaxval）来记录这些信息，themaxval[i][j]表示区间[i, j]内的最大权值，关键就是如何实现这个表，以及维护它。实现还是比较简单的，可以直接在输入数据(nums[i])的时候创建这个表，因为只需要判断nums[i]与themaxval[k][i - 1]的大小关系就可以得出themaxval[k][i]的值（themaxval[k][i] = max(nums[i], themaxval[k][i - 1]）；难的部分是在维护，也就是操作1的实现，其实是有一定的规律的，同样出于是错误方法的原因所以就不说了，有兴趣的可以自个推推，或者是留言不耻下问一下我，哈哈哈。

接下来就是正规解法了——线段树，先看一下百度百科关于线段树的图示吧。
我刚开始看到线段树的定义的时候，我就觉得跟我第二种解法是有点类似的，只不过我是记录了所有的区间，而线段树只是每次将区间都一分为二，分别去记录这两部分区间的信息。想了一下我才发现原来这样也可以，而且创建过程也挺方便的（虽然我建树建了挺久的…），维护也不难，所以就动手码了一下，结果就过了。

解题思路：直接看代码吧

#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
#include<string>
#include<cmath>
#include<deque>
#include<utility>

using namespace std;

class TreeNode {
public:
	TreeNode(size_t la = 0, size_t ra = 0, int val = 0) : leftedge(la), rightedge(ra), maxVal(val), leftnode(nullptr), rightnode(nullptr) {}
public:
	size_t leftedge;
	size_t rightedge;
	int maxVal;
	TreeNode *leftnode;
	TreeNode *rightnode;
};

class LineTree {
public:
	LineTree(const vector<int> &nums);
	~LineTree();
public:
	TreeNode *rootnode;
};

inline const int &get_max(const int &a, const int &b) {
	return a > b ? a : b;
}

//根据数据创建线段树
void creat_tree(const vector<int> &nums, TreeNode *fatherNode) {
	size_t areasize = fatherNode->rightedge - fatherNode->leftedge + 1;
	fatherNode->leftnode = new TreeNode;
	fatherNode->rightnode = new TreeNode;
	if (areasize == 2) {
		fatherNode->leftnode->leftedge = fatherNode->leftnode->rightedge = fatherNode->leftedge;
		fatherNode->leftnode->maxVal = nums[fatherNode->leftedge];
		fatherNode->rightnode->leftedge = fatherNode->rightnode->rightedge = fatherNode->rightedge;
		fatherNode->rightnode->maxVal = nums[fatherNode->rightedge];
	}
	else if (areasize == 3) {
		fatherNode->leftnode->leftedge = fatherNode->leftedge; fatherNode->leftnode->rightedge = fatherNode->leftedge + 1;
		creat_tree(nums, fatherNode->leftnode);
		fatherNode->rightnode->leftedge = fatherNode->rightnode->rightedge = fatherNode->rightedge;
		fatherNode->rightnode->maxVal = nums[fatherNode->rightedge];
	}
	else {
		fatherNode->leftnode->leftedge = fatherNode->leftedge;
		fatherNode->leftnode->rightedge = (fatherNode->leftedge + fatherNode->rightedge) / 2;
		fatherNode->rightnode->leftedge = fatherNode->leftnode->rightedge + 1;
		fatherNode->rightnode->rightedge = fatherNode->rightedge;
		creat_tree(nums, fatherNode->leftnode);
		creat_tree(nums, fatherNode->rightnode);
	}
	fatherNode->maxVal = get_max(fatherNode->leftnode->maxVal, fatherNode->rightnode->maxVal);
}


LineTree::LineTree(const vector<int> &nums){
	rootnode = new TreeNode(0, nums.size() - 1);
	creat_tree(nums, rootnode);
}

//释放空间
void delnode(TreeNode *fathernode) {
	if (fathernode == nullptr) return;
	delnode(fathernode->leftnode);
	delnode(fathernode->rightnode);
	delete fathernode;
	fathernode = nullptr;
	return;
}

LineTree::~LineTree() {
	delnode(rootnode);
}

//更改权值——找到叶子节点，然后向上更新最大值
void change_val(TreeNode *tnode, const int &pos, const int &val) {
	if (tnode->leftedge == tnode->rightedge) {
		if (tnode->leftedge == pos) 
			tnode->maxVal = val;
	}
	else {
		size_t midedge = (tnode->leftedge + tnode->rightedge) / 2;
		if (pos <= midedge) change_val(tnode->leftnode, pos, val);
		else change_val(tnode->rightnode, pos, val);
		tnode->maxVal = get_max(tnode->leftnode->maxVal, tnode->rightnode->maxVal);
	}
}

//计算区间权值和
int figure_sum(const vector<int> &nums, const size_t b, const size_t e) {
	int sum = 0;
	for (size_t i = b; i <= e; ++i)
		sum += nums[i];
	return sum;
}

//查找区间最大权值
/*
	区间会有四种情况：
	第一种就是刚好等于结点所表示的空间；
	第二种就是被包含在结点所表示的区间的左半部分；
	第三种就是右半部分；
	第四种就是既在左半部分，又在右半部分。
	
	前三种都很好解决，主要说一下第四种，结点所表示的区间的中间值记为midarea，
 将指定区间[b,e]分为[b, midarea]和[midarea + 1, e]，然后往下搜索。
*/
int search_max_val(TreeNode *tnode, const size_t b, const size_t e) {
	if (b == tnode->leftedge && e == tnode->rightedge) return tnode->maxVal;
	size_t midedge = (tnode->rightedge + tnode->leftedge) / 2;
	if (e <= midedge) return search_max_val(tnode->leftnode, b, e);
	else if (b > midedge) return search_max_val(tnode->rightnode, b, e);
	else return get_max(search_max_val(tnode->leftnode, b, midedge), search_max_val(tnode->rightnode, midedge + 1, e));
	
}

int main() {
	
	int n, m;  cin >> n >> m;
	vector<int> nums(n, 0);
	for (int i = 0; i < n; ++i)
		cin >> nums[i];
	LineTree ltree(nums);
	
	vector<vector<int> > question(m, vector<int>(3, 0));
	for (int i = 0; i < m; ++i) {
		cin >> question[i][0] >> question[i][1] >> question[i][2];
	}
	
	for (int i = 0; i < m; ++i) {
		switch (question[i][0])
		{
		case 1:
			change_val(ltree.rootnode, question[i][1] - 1, question[i][2]);
			nums[question[i][1] - 1] = question[i][2];
			break;
		case 2:
			cout << figure_sum(nums, question[i][1] - 1, question[i][2] - 1) << endl;
			break;
		case 3:
			cout << search_max_val(ltree.rootnode, question[i][1] - 1, question[i][2] - 1) << endl;
			break;
		default:
			break;
		}
	}
	

	return 0;
}

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

做完之后我去查了别人的实现方式，看到了别人是直接用数组做的，其实我也知道可以用数组来存储二叉树，但是我用得比较多的是用来存储完全二叉树，线段树并不是完全二叉树，所以对于这道题我一开始就没想过用数组来进行存储，因为觉得会浪费空间，但是看了之后才发现原来对于这道题其实也是可行的，计算了一下发现其实也不会浪费多少空间，相反实现过程还简便了许多，算是长知识了。