博客
关于我
线段树(高级二叉树)
阅读量:366 次
发布时间:2019-03-04

本文共 3987 字,大约阅读时间需要 13 分钟。

简单线段树(无pushdown)

线段树的每个结点代表一个区间。

每个结点存着对应区间相关信息。
线段树的三部分:根结点、左子树、右子树。
由于树下又可以分树,故而可以用递归实现。
在这里插入图片描述
在这里插入图片描述

单点修改、区间查询:

#include
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 ) / 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 ) / 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 query_tree( int arr[] , int tree[] , int node , int start , int end , int L , int R ){ if( R < start || L > end ) { return 0 ; } else { if( L <= start && end <= R ) { return node ; } else { if( start == end ) { return tree[node] ; } else { int mid = ( start + end ) / 2 ; int left_node = 2 * node + 1 ; int right_node = 2 * node + 2 ; int sum_left = query_tree( arr , tree , left_node , start , mid , L , R ) ; int sum_right = query_tree( arr , tree , right_node , mid + 1 , end , L , R ) ; return sum_left + sum_right ; //求和 } } }}

题:

很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。

这让很多学生很反感。

不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。

Input

本题目包含多组测试,请处理到文件结束。
在每个测试的第一行,有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 ),分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取’Q’或’U’) ,和两个正整数A,B。
当C为’Q’的时候,表示这是一条询问操作,它询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少。
当C为’U’的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。

Output

对于每一次询问操作,在一行里面输出最高成绩。

Sample Input

5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5

Sample Output

5
6
5
9

Hint

Huge input,the C function scanf() will work better than cin

#include
#include
using namespace std;int arr[200005];int tree[100000000]={ 0};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)/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]=max(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)/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]=max(tree[left_node],tree[right_node]); }} int query(int arr[],int tree[],int node,int start,int end,int L,int R){ if(R
end) { return 0; } else { if(L<=start&&R>=end) { return tree[node]; } else { if(start==end) { return tree[node]; } else { int mid=(start+end)/2; int left_node=2*node+1; int right_node=2*node+2; int max_left=query(arr,tree,left_node,start,mid,L,R); int max_right=query(arr,tree,right_node,mid+1,end,L,R); return max(max_left,max_right); } } }}int main(){ int n,m,i; while(scanf("%d%d",&n,&m)!=EOF) { for(i=0;i
>e; scanf("%d%d",&x,&y); if(e=='U') { update_tree(arr,tree,0,0,n-1,x-1,y); } if(e=='Q') { v=query(arr,tree,0,0,n-1,x-1,y-1); cout<
<

转载地址:http://rwbg.baihongyu.com/

你可能感兴趣的文章
MySQL“被动”性能优化汇总
查看>>
MySQL、HBase 和 Elasticsearch:特点与区别详解
查看>>
MySQL、Redis高频面试题汇总
查看>>
MYSQL、SQL Server、Oracle数据库排序空值null问题及其解决办法
查看>>
mysql一个字段为空时使用另一个字段排序
查看>>
MySQL一个表A中多个字段关联了表B的ID,如何关联查询?
查看>>
MYSQL一直显示正在启动
查看>>
MySQL一站到底!华为首发MySQL进阶宝典,基础+优化+源码+架构+实战五飞
查看>>
MySQL万字总结!超详细!
查看>>
Mysql下载以及安装(新手入门,超详细)
查看>>
MySQL不会性能调优?看看这份清华架构师编写的MySQL性能优化手册吧
查看>>
MySQL不同字符集及排序规则详解:业务场景下的最佳选
查看>>
Mysql不同官方版本对比
查看>>
MySQL与Informix数据库中的同义表创建:深入解析与比较
查看>>
mysql与mem_细说 MySQL 之 MEM_ROOT
查看>>
MySQL与Oracle的数据迁移注意事项,另附转换工具链接
查看>>
mysql丢失更新问题
查看>>
MySQL两千万数据优化&迁移
查看>>
MySql中 delimiter 详解
查看>>
MYSQL中 find_in_set() 函数用法详解
查看>>