备孕百度之星-9月21日

树状数组

#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;
//	}
}