Ihate it

区间最值

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;
const int N = 2e5+10;
int n,m,a[N],tree[N];
int lowbit(int x){return x&(-x);}
void update1(int x,int value){
  while (x <= n){
    tree[x] = value;
    for (int i = 1; i < lowbit(x); i<<=1)          //标准的是记录[x - lowbit(x) + 1 , x] 中的和，求最值改成范围内的最大值
      tree[x] = max(tree[x],tree[x-i]);            //用子节点更新自己
    x += lowbit(x);                                //父节点
  }
}
int query1(int L,int R) {
  int ans = 0;
  while (L <= R){
    ans = max(ans, a[R]);                          //R - L < lowbit(R):max(a[R], query1([L , R - 1))
    R --;
    while (R -L >= lowbit(R)){
      ans = max(ans, tree[R]);                     //R - L >= lowbit(R):max(tree[R], query1([L , lowbit(R)))
      R -= lowbit(R);
    }
  }
  return ans;
}
int main(){
  while(~scanf("%d%d",&n,&m)) {                     //数字个数、操作数
    memset(tree,0,sizeof(tree));                    //初始化
    for(int i=1; i<=n; i++){ scanf("%d",&a[i]); update1(i,a[i]); }
    while(m--){
      char s[5];int A,B; scanf("%s%d%d",s,&A,&B);
      if(s[0]=='Q') printf("%d\n",query1(A,B));     //查询
      else{ a[A]=B; update1(A,B);}                  //更新
    }
  }
  return 0;
}

笔记：区间求最值，树状数组的tree[]的储存方式修改成区间最大值，而不是[x – lowbit(x) + 1 , x]的区间和，查询也要分成两种情况，一种是区间内包含直连的子节点，直接用tree[R]，另一种是上一个关系不存在，R逐步向前推进寻找最值