线段树
下面是一个简易模板，用数组实现线段树，可以轻易求出区间和以及修改某个位置的值。
P.S. 这是我在B站学了灯神的......链接在这里 ("https://www.bilibili.com/video/av47331849" 【数据结构】线段树（Segment Tree）)
#include<bits/stdc++.h>
using namespace std;
#define max_len 1000
void build_tree(int arr[],int tree[],int node,int start,int end){
if(start == end){
tree[node] = arr[start];
}
else {
int mid=start+end;mid=mid/2;
int left_node = 2 * node + 1 ;
int right_node = 2 * node + 2 ;
build_tree(arr, tree, left_node, start, mid );
build_tree(arr, tree, right_node, mid + 1, end );
tree[node] = tree[left_node] + tree[right_node];
}
}
void update_tree(int arr[],int tree[],int node,int start,int end,int idx ,int val){
if(start == end){
arr[idx]=val;
tree[node]=val;
}
else {
int mid=start+end;mid=mid/2;
int left_node = 2 * node + 1 ;
int right_node = 2 * node + 2 ;
if(idx>=start&&idx<=mid){
update_tree(arr,tree,left_node,start,mid,idx,val);
}
else {
update_tree(arr,tree,right_node,mid+1,end,idx,val);
}
tree[node] = tree[left_node] + tree[right_node];
}
}
int sum_tree(int arr[], int tree[], int node, int start, int end, int L, int R){
if(R<start||L>end){
return 0;
}
else if(start==end){
return tree[node];
}else if(L<=start&&end<=R){
return tree[node];
}
else {
int mid=(start+end)/2;
int left_node=2 * node + 1 ;
int right_node= 2 * node + 2 ;
int sum_left=sum_tree(arr,tree,left_node,start,mid,L,R);
int sum_right=sum_tree(arr,tree,right_node,mid+1,end,L,R);
return sum_left+sum_right;
}
}
int main(){
int arr[]={1, 3, 5, 7, 9, 11};
int size = 6;
int tree[max_len ]={0};
build_tree(arr, tree, 0, 0, size-1 );
for(int i=0;i<15;i++)printf("tree %d = %d
",i ,tree[i]);
printf("
");
update_tree(arr,tree,0,0,size-1,4,6);
for(int i=0;i<15;i++)printf("tree %d = %d
",i ,tree[i]);
printf("
");
int s=sum_tree(arr,tree,0,0,size-1,2,5);
printf("%d",s);
}
现在来看一个实训题目
题目链接：("https://pintia.cn/problem-sets/1119845950595133440/problems/1119846095604805632")
题目 7-4 查询成绩(II) （40 分)
描述：
又到了每学期的期中考试的日子了，这天小q的老师刚批阅完期中考试卷，老师将考试分数列了出来，想要小q同学分析一下这次同学们的考试情况如何。
这可难倒了小q同学，你能帮帮他吗？
老师将会给你提供一份成绩单，然后老师将会问你其中某些同学中，最高分与最低分两个分数之间的平均分是多少（只计算两位同学的成绩之和的平均值，且答案只保留整数位），你能回答上来吗？
同时，由于计分有误，在询问时还有可能更改某位同学的分数，所以你在输出答案的时候应该是按最新版本的成绩单为准输出
这里要求区间最大值和最小值的平均数（保留到整数）并且要多次修改某一个值
输入格式:
每组数据第一行两个数字n和q，表示拥有成绩的人数和老师的命令次数 (1≤n≤10^6) (1≤q≤2∗10^4)
接下来一行，n个不大于100的正整数，表示各位同学的成绩
接着q行，有两种操作：询问或者更新
若本次命令是询问成绩平均值，则会先输入一个0表示本次操作为询问，之后跟着两个正整数l和r，表示询问l到r区间内，最高分和最低分的这两位同学的平均分
若本次命令是更改某位同学的成绩，则会先输出一个1表示本次操作为更改值，之后跟着两个正整数a和b，表示第a位同学的成绩改为b
输出格式:
对于每个询问命令，请输出对应的结果，每个结果占一行
结果只保留至整数部分
输入样例:
5 3
100 100 100 100 100
0 1 2
1 1 75
0 1 2
输出样例:
100
87
不难想到要线段树上场，不然时间会炸（别问我怎么知道的）
#include<bits/stdc++.h>
using namespace std;
#define max_len 10000000
int minn=100,maxx=0;
int arr[1005000]={0};
int bigtree[max_len]={0},smatree[max_len]={0};
void build_bigtree(int arr[],int tree[],int node,int start,int end){
if(start == end){
tree[node] = arr[start];
}
else {
int mid=start+end;mid=mid/2;
int left_node = 2 * node + 1 ;
int right_node = 2 * node + 2 ;
build_bigtree(arr, tree, left_node, start, mid );
build_bigtree(arr, tree, right_node, mid + 1, end );
tree[node] =max( tree[left_node] ,tree[right_node]);
}
}
void build_smatree(int arr[],int tree[],int node,int start,int end){
if(start == end){
tree[node] = arr[start];
}
else {
int mid=start+end;mid=mid/2;
int left_node = 2 * node + 1 ;
int right_node = 2 * node + 2 ;
build_smatree(arr, tree, left_node, start, mid );
build_smatree(arr, tree, right_node, mid + 1, end );
tree[node] = min(tree[left_node] , tree[right_node]);
}
}
void update_bigtree(int arr[],int tree[],int node,int start,int end,int idx ,int val){
if(start == end){
arr[idx]=val;
tree[node]=val;
}
else {
int mid=start+end;mid=mid/2;
int left_node = 2 * node + 1 ;
int right_node = 2 * node + 2 ;
if(idx>=start&&idx<=mid){
update_bigtree(arr,tree,left_node,start,mid,idx,val);
}
else {
update_bigtree(arr,tree,right_node,mid+1,end,idx,val);
}
tree[node] = max(tree[left_node] , tree[right_node]);
}
}
void update_smatree(int arr[],int tree[],int node,int start,int end,int idx ,int val){
if(start == end){
arr[idx]=val;
tree[node]=val;
}
else {
int mid=start+end;mid=mid/2;
int left_node = 2 * node + 1 ;
int right_node = 2 * node + 2 ;
if(idx>=start&&idx<=mid){
update_smatree(arr,tree,left_node,start,mid,idx,val);
}
else {
update_smatree(arr,tree,right_node,mid+1,end,idx,val);
}
tree[node] =min(tree[left_node] , tree[right_node]);
}
}
void sum_bigtree(int arr[], int tree[], int node, int start, int end, int L, int R){
// printf("maxn=%d
",maxx);
if(R<start||L>end){
return ;
}else if(L<=start&&end<=R){
if(tree[node]>maxx)maxx=tree[node];
return ;
}else if(start==end){
if(tree[node]>maxx)maxx=tree[node];
return ;
}
else {
int mid=(start+end)>>1;
int left_node=2*node+1;
int right_node=2*node+2;
sum_bigtree(arr,tree,left_node,start,mid,L,R);
sum_bigtree(arr,tree,right_node,mid+1,end,L,R);
}
}
void sum_smatree(int arr[], int tree[], int node, int start, int end, int L, int R){
// printf("minn=%d
",minn);
if(R<start||L>end){
return ;
}else if(L<=start&&end<=R){
if(tree[node]<minn)minn=tree[node];
return ;
}else if(start==end){
if(tree[node]<minn)minn=tree[node];
return ;
}
else {
int mid=(start+end)/2;
int left_node=2*node+1;
int right_node=2*node+2;
sum_smatree(arr,tree,left_node,start,mid,L,R);
sum_smatree(arr,tree,right_node,mid+1,end,L,R);
}
}
int main(){
int n,q;
scanf("%d %d",&n,&q);
int size = n;
for(int i=0;i<n;i++)scanf("%d",&arr[i]);
build_bigtree(arr, bigtree, 0, 0, size-1 );
build_smatree(arr, smatree, 0, 0, size-1 );
for(int i=0;i<q;i++){
int o1,o2,o3;
minn=100,maxx=0;
scanf("%d %d %d",&o1,&o2,&o3);
if(o1==0){
sum_bigtree(arr,bigtree,0,0,size-1,o2-1,o3-1);
sum_smatree(arr,smatree,0,0,size-1,o2-1,o3-1);
int s=maxx+minn;
printf("%d
",s/2);
}
if(o1==1){
update_bigtree(arr,bigtree,0,0,size-1,o2-1,o3);
update_smatree(arr,smatree,0,0,size-1,o2-1,o3);
}
}
return 0;
}