题目链接:这道题是线段树,树状数组最基础的问题
两种分类方式:按照更新对象和查询对象
单点更新,区间查询;
区间更新,单点查询;
按照整体维护的对象:
维护前缀和;
维护区间最值.
线段树模板代码
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define re(i,n) for(int i=0;i<n;i++)
typedef long long ll;
* 1e5 + ;
#define lson(x) x<<1,f,mid
#define rson(x) x<<1|1,mid+1,t
int n, m;
];
int x, y;
int ans;
void build(int r, int f, int t){
if (f == t){
scanf("%d", &tr[r]);
return;
}
;
build(lson(r)),build(rson(r));
tr[r] = max(tr[r << ], tr[r << | ]);
}
void query(int r, int f, int t){
if (f >= x&&t <= y){
ans = max(ans, tr[r]);
return;
}
;
if (x <= mid)query(lson(r));
if (y > mid)query(rson(r));
}
void update(int r, int f, int t){
if (f == t){
tr[r] = y;
return;
}
;
if (x<= mid)update(lson(r));
else update(rson(r));
tr[r] = max(tr[r << ], tr[r << | ]);
}
int main(){
//freopen("in.txt", "r", stdin);
while (cin >> n >> m){
build(, , n);
while (m--){
]; scanf("%s%d%d", op,&x,&y);
] == 'Q'){
if (x > y)swap(x, y);
ans = -;
query(, , n);
printf("%d\n", ans);
}
else{
update(, , n);
}
}
}
;
}
树状数组区间最值模板代码
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
*1e5+;
typedef long long ll;
#define re(i,n) for(int i=0;i<n;i++)
int a[maxn], c[maxn];
/*
a里面存放本值,c里面维护最值
*/
int n, q;
int lowbit(int x){
return x&-x;
}
void redo(int i){
c[i] = i;
; j < lowbit(i); j <<= )
if (a[c[i - j]]>a[c[i]])c[i] = c[i - j];
}
void init(){
; i <= n; i++){
redo(i);
}
}
void update(int x, int y){
bool big = y > a[x];
a[x] = y;
int i = x;
if (big){
/*
这个地方如果错写成a[c[i]]<y就会导致无法传递上去,因为一开始时就是a[c[i]]==y.
*/
while (i<=n&&a[c[i]] <= y)c[i] = x, i += lowbit(i);
}
else{
while (i<=n&&c[i] == x)redo(i), i += lowbit(i);
}
}
int query(int l, int r){
int ans = a[r];
while (l<=r){
while (r - lowbit(r) >= l){
ans = max(a[c[r]], ans);
r -= lowbit(r);
}
ans = max(a[r], ans);//根节点
r--;//向下走一步
}
return ans;
}
int main(){
freopen("in.txt", "r", stdin);
){
re(i, n)scanf(]);
init();
;
while (q--){
]; int x, y;
qi++;
scanf("%s%d%d", &op, &x, &y);
] == 'U'){
update(x, y);
}
else{
int ans = query(x, y);
printf("%d\n", ans);
}
}
}
;
}
复杂度是O(lgn*lgn).这道题数据好像有点弱,因为错误的代码也能过这道题.
zwk线段树模板
zwk线段树巧妙之处在于开区间写法,对于长度为N的线段,初始化时,共N+2片叶子:1和N+2空着,2~N+1才是本体,是实实在在的数据.张昆玮说了:如果有1023个数据,那就要有2048片叶子.空间要开到(N+2)*4才行.虽然费了点空间,但编程简洁了.
根节点(1号结点)和每层的第一个节点和最后一个节点是哨兵节点,永远都不会访问到它们.它们的存在只是方便编程.老子曰:将欲取之,必先予之.一言以蔽之,就是两端边界处的节点都是哨兵节点,这是开区间方便编程导致的.
那么闭区间写法行不行呢?对于长度为N的线段,1~N全部用上,查询时闭区间可以转换成开区间.如果有1023个数,那就只需要开辟1024片叶子的树状数组.开区间=闭区间-两个端点.若无论如何都更新两个端点,那就会导致更新的东西有点靠下,这对于结果并没什么影响.需要注意l==r的情形.
zwk开区间写法
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
* 1e5 + ;
typedef long long ll;
#define re(i,n) for(int i=0;i<n;i++)
];
int n, q, sz;
void update(int x, int v){
x += sz;
a[x] = v;
){
x >>= ;
a[x] = max(a[x << ], a[x << | ]);
}
}
int query(int l, int r){
l += sz - , r += sz + ;
;
){//当两人不是兄弟时
){
ans = max(ans, a[l ^ ]);
}
){
ans = max(ans, a[r ^ ]);
}
l >>= , r >>= ;
}
return ans;
}
int main(){
//freopen("in.txt", "r", stdin);
){
sz = ; )sz <<= ;
re(i, n){
scanf(]);
}
); i++)a[i + sz+] = ;
; i>; i--){
a[i] = max(a[i << ], a[i << | ]);
}
while (q--){
]; int x, y;
scanf("%s%d%d", op, &x, &y);
] == 'U'){
update(x, y);
}
else{
int ans = query(x, y);
printf("%d\n", ans);
}
}
}
;
}
zwk闭区间写法:下面的代码有bug.能过题.
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
* 1e5 + ;
typedef long long ll;
#define re(i,n) for(int i=0;i<n;i++)
];
int n, q, sz;
void update(int x, int v){
x += sz-;
a[x] = v;
){
x >>= ;
a[x] = max(a[x << ], a[x << | ]);
}
}
int query(int l, int r){
l += sz - , r += sz - ;
int ans =max(a[l],a[r]); //查询时先把两个端点给处理掉,就相当于开区间了.
/*
这个地方的不同决定了两种写法,我觉得没有必要开区间.闭区间预处理一下就很好.
这个地方如果l==r,就会产生死循环.但是我这么写,这道题却过了.*/
){//当两人不是兄弟时
){
ans = max(ans, a[l ^ ]);
}
){
ans = max(ans, a[r ^ ]);
}
l >>= , r >>= ;
}
return ans;
}
void init(){
sz = ; ;
re(i, n){
scanf("%d", &a[i + sz]);//在1~N之间存放数据
}
); i++)a[i + sz ] = ;
; i>; i--){
a[i] = max(a[i << ], a[i << | ]);
}
}
int main(){
freopen("in.txt", "r", stdin);
){
init();
while (q--){
]; int x, y;
scanf("%s%d%d", op, &x, &y);
] == 'U'){
update(x, y);
}
else{
int ans = query(x, y);
printf("%d\n", ans);
}
}
}
;
}