树状数组
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int a[500005], b[500005];
int n, m, tag;
int ask(int x){
int res = 0;
for(; x; x -= x & -x) res += b[x];
return res;
}
int add(int x, int y){
for(; x <= n; x += x & -x) b[x] += y;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
//b是累加的前缀和
for(int i = 0; i < m; i++){
cin >> tag;
if(tag == 1){
int x, y, z;
cin >> x >> y >> z;
add(x, z);
add(y+1, -z);
}else{
int index;
cin >> index;
int res = a[index] + ask(index);
cout << res << endl;
}
}
}
线段树
#include<iostream>
#include<cstring>
using namespace std;
const int N = 500;
int a[N];
int n;
struct segt{
int l, r;
int dat;
}t[4 * N];
void build(int p, int l, int r){
t[p].l = l;
t[p].r = r;
if(l == r) {
t[p].dat = a[l];
return ;//叶子节点
}
int mid = l + (r-l)/2;
build(2 * p, l, mid);
build(2 * p + 1, mid + 1, r);
t[p].dat = max(t[2*p].dat, t[2*p+1].dat);
}
void change(int p, int x, int v){
if(t[p].l == t[p].r) {
t[p].dat = v;
return ;
}
int mid = t[p].l + (t[p].r - t[p].l) / 2;
if(x <= mid)
change(2*p, x, v);
else
change(2*p + 1, x, v);
t[p].dat = max(t[2*p].dat, t[2*p+1].dat);
}
int ask(int p, int l, int r){
if(l <= t[p].l && r >= t[p].r) {
return t[p].dat;
}
int val = -(1<<30);
//计算两种子节点的包含状态
int mid = t[p].l + (t[p].r - t[p].l) / 2;
if(l <= mid) val = max(val, ask(2*p, l, r));
if(r > mid) val = max(val, ask(2*p+1, l, r));
return val;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
//构建树
build(1, 1, n);
for(int i = 0; i < 20; i++){
cout << t[i].l << t[i].r << t[i].dat << endl;
}
//单点修改
change(1, 2, 5);//把2位置改成5
//区间查询
int res = ask(1, l, r);//返回1-5位置的最大值
}
线段树（ch4301）
#include<iostream>
#include<cstring>
using namespace std;
const int N = 50000;
int a[N];
int n;
struct segt{
int l, r;
int dat, sum, lmax, rmax;
}t[4 * N];
void build(int p, int l, int r){
t[p].l = l;
t[p].r = r;
if(l == r) {
t[p].sum = a[l];
t[p].lmax = a[l];
t[p].rmax = a[l];
t[p].dat = a[l];
return ;//叶子节点
}
int mid = l + (r-l)/2;
build(2 * p, l, mid);
build(2 * p + 1, mid + 1, r);
t[p].dat = max(max(t[2*p].dat, t[2*p+1].dat), t[2*p].rmax + t[2*p+1].lmax);
t[p].sum = t[2*p].sum + t[2*p+1].sum;
t[p].lmax = max(t[2*p].lmax, t[2*p].sum + t[2*p+1].lmax);
t[p].rmax = max(t[2*p+1].rmax, t[2*p+1].sum + t[2*p].rmax);
}
void change(int p, int x, int v){
if(t[p].l == t[p].r) {
t[p].dat = v;
t[p].sum = v;
t[p].lmax = v;
t[p].rmax = v;
return ;
}
int mid = t[p].l + (t[p].r - t[p].l) / 2;
if(x <= mid)
change(2*p, x, v);
else
change(2*p + 1, x, v);
t[p].dat = max(max(t[2*p].dat, t[2*p+1].dat), t[2*p].rmax + t[2*p+1].lmax);
t[p].sum = t[2*p].sum + t[2*p+1].sum;
t[p].lmax = max(t[2*p].lmax, t[2*p].sum + t[2*p+1].lmax);
t[p].rmax = max(t[2*p+1].rmax, t[2*p+1].sum + t[2*p].rmax);
}
segt ask(int x, int y, int p, int l, int r){
if(x<=l&&r<=y) return t[p];
int mid=(l+r)>>1;
if(y<=mid) return ask(x,y,2*p,l,mid);
if(mid<x) return ask(x,y,2*p+1,mid+1,r);
segt L=ask(x,mid,2*p,l,mid),R=ask(mid+1,y,2*p+1,mid+1,r),res;
res.sum=L.sum+R.sum;
res.lmax=max(L.lmax,L.sum+R.lmax);
res.rmax=max(R.rmax,R.sum+L.rmax);
res.dat=max(L.rmax+R.lmax,max(L.dat,R.dat));
return res;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
//构建树
build(1, 1, n);
int m;
cin >> m;
for(int i = 0; i < m ; i++){
int tag, x, y;
cin >> tag >> x >> y;
if(tag == 0){
change(1,x,y);
}else{
cout << ask(x,y, 1,1,n).dat << endl;
}
}
// cout << "===" << endl;
// for(int i = 0; i < 20; i++){
// cout << t[i].l << "==" << t[i].r << "==" << t[i].dat << endl;
// }
}
