算法训练 操作格子  

时间限制：1.0s   内存限制：256.0MB

      

问题描述

有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。

---

 

　　线段树，点更新。

　　线段树每一个节点代表一个区间，并存储有这个区间的特定值，例如这个区间最大值，区间和等等……而这道题的特定值有两个，权值和 和 最大权值。

　　思路：

　　没有什么特殊的地方，按照正常的线段树的思路来做即可。

　　* 每个节点存储权值和val，最大权值mx；

　　1.更新的时候，递归找到底，val和mx一起修改，然后一层层的返回的时候，用Push_up()，不断更新val和mx；

　　2.查询权值和的时候，递归往下找，直到找到要查询的区间为止，返回该区间节点的权值和val；

　　3.查询最大权值的时候，也是递归向下找，找到查询区间之后，返回节点的最大权值mx。

　　以上就为基本的步骤了，另外注意Push_up()的编写。

　　写这道题的时候，线段树用的还不是很熟，第一遍写完之后，测试数据不对，又修改了很多地方才通过。所以做线段树的题，要注意好细节。总的来说，这道题是一道不错的线段树的练手题。

　　代码：

1 #include 
      
         2 #include 
       
          3 using namespace std;  4 #define MAXN 100010  5 struct Node{  6     int left,right;  7     int val,mx; //权值和最大值  8 };  9 Node tree[MAXN*3+1]; 10 int Max(int a,int b)    //返回两数较大值 11 { 12     return a>b?a:b; 13 } 14 void Push_up(int d) 15 { 16     tree[d].val = tree[d<<1].val + tree[d<<1|1].val; 17     tree[d].mx = Max(tree[d<<1].mx , tree[d<<1|1].mx); 18 } 19 void Init(int d,int l,int r)    //初始化线段树 20 { 21     if(l==r){ 22         tree[d].left = l; 23         tree[d].right = r; 24         scanf("%d",&tree[d].val);   //读取数据 25         tree[d].mx = tree[d].val; 26         return ; 27     } 28  29     int mid = (l+r)/2; 30     tree[d].left = l; 31     tree[d].right = r; 32     Init(d<<1,l,mid); 33     Init(d<<1|1,mid+1,r); 34     Push_up(d); 35 } 36 void Update(int d,int l,int r,int x)  //1.修改一个格子的权值。[l,r]为要找的区间，在这道题里l==r。x为要修改的值 37 { 38     if(tree[d].left==l && tree[d].right==r){    //找到区间。 39         tree[d].val = x; 40         tree[d].mx = x; 41         return ; 42     } 43     if(tree[d].left == tree[d].right){  //没找到区间 44         return ; 45     } 46  47     int mid = (tree[d].left+tree[d].right)/2; 48     if(mid>=r){ //去左区间 49         Update(d<<1,l,r,x); 50     } 51     else if(mid
        
         =r){ 71         return Query_sum(d<<1,l,r); 72     } 73     else if(mid
         
          =r){ 91         return Query_max(d<<1,l,r); 92     } 93     else if(mid
         
        
       
      

 

Freecode :