线段树-笔记

常规
1

线段树模板

可能会有语法错误 供大家以后学习使用

自己

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const int N=1e5+5;
int n,a[N];
struct Node{
	int l,r;
	int maxn,sum;
	int lazy_tag=0;
}tre[N<<2];
void pushup(int pos){
	tre[pos].maxn=max(tre[pos<<1].maxn,tre[pos<<1|1].maxn);
	tre[pos].sum=tre[pos<<1].sum+tre[pos<<1|1].sum;
}
void pushdown(int pos){
	if(tre[pos].lazy_tag==0) return ;
	tre[pos<<1].lazy_tag+=tre[pos].lazy_tag;
	tre[pos<<1|1].lazy_tag+=tre[pos].lazy_tag;
	tre[pos<<1].sum+=tre[pos].lazy_tag*(tre[pos<<1].r-tre[pos<<1].l+1);
	tre[pos<<1|1].sum+=tre[pos].lazy_tag*(tre[pos<<1|1].r-tre[pos<<1|1].l+1);
	tre[pos<<1].maxn+=tre[pos].lazy_tag;
	tre[pos<<1|1].maxn+=tre[pos].lazy_tag;
	tre[pos].lazy_tag=0;
}
//建树 
void build(int l,int r,int pos){
	tre[pos].l=l;
	tre[pos].r=r;
	if(l==r){
		tre[pos].maxn=a[l];
		tre[pos].sum=a[l];
		return ;
	}
	int mid=l+r>>1;
	build(l,mid,pos<<1);
	build(mid+1,r,pos<<1|1);
	pushup(pos);
}
//查询 
int queryMax(int pos,int l,int r){
	if(tre[pos].r<l||tre[pos].l>r) return 0;
	if(tre[pos].l>=l&&tre[pos].r<=r) return tre[pos].maxn;
	pushdown(pos);
	return max(queryMax(pos<<1,l,r),queryMax(pos<<1|1,l,r));
}
int querySum(int pos,int l,int r){
	if(tre[pos].r<l||tre[pos].l>r) return 0;
	if(tre[pos].l>=l&&tre[pos].r<=r) return tre[pos].sum;
	pushdown(pos);
	return querySum(pos<<1,l,r)+querySum(pos<<1|1,l,r);
}
//单点修改 
void update(int pos,int x,int val){
	if(tre[pos].r==tre[pos].l){
		tre[pos].maxn=val;
		tre[pos].sum=val;
		return ;
	}
	int mid=tre[pos].l+tre[pos].r>>1;
	if(x<=mid) update(pos<<1,x,val);
	else update(pos<<1|1,x,val);
	
	pushup(pos);
	
}
void modify(int pos,int l,int r,int val){
	if(tre[pos].r<l||tre[pos].l>r) return ;
	if(tre[pos].l>=l&&tre[pos].r<=r){
		tre[pos].sum+=(tre[pos].r-tre[pos].l+1)*val;
		tre[pos].maxn+=val;
		tre[pos].lazy_tag+=val;
		return ;
	}
	pushdown(pos);
	modify(pos<<1,l,r,val);
	modify(pos<<1|1,l,r,val);
	pushup(pos);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,n,1);
	int t;
	cin>>t;
	while(t--){
		int op;
		cin>>op;
		if(op==1){
			int l,r;
			cin>>l>>r;
			cout<<queryMax(1,l,r)<<endl;
		}
		else if(op==2){
			int l,r;
			cin>>l>>r;
			cout<<querySum(1,l,r)<<endl;
		}
		else{
			int pos,v;
			cin>>pos>>v;
			update(1,pos,v);
		}
	}
  
//    update(1,pos,val);
//    query(1,l,r);
}

标程

#include <iostream>

using namespace std;

const int N = 1e5 + 5;
int a[N];
//代表当前区间a

struct Node {
    int l, r;
    int max, min;
    int sum;
    int lazy_tag = 0;
} tre[N << 2];

//区间信息从下往上，如果下层信息被修改（如端点修改，建树等，需要更新同步上层，以维护区间信息）
void pushup(int pos) {
    tre[pos].max = max(tre[pos << 1].max, tre[pos << 1 | 1].max);
    tre[pos].min = max(tre[pos << 1].min, tre[pos << 1 | 1].min);
    tre[pos].sum = tre[pos << 1].sum + tre[pos << 1 | 1].sum;
}

//建立线段树:
void build(int l, int r, int pos) {
    tre[pos].l = l;
    tre[pos].r = r;

    if (l == r) {
        tre[pos].max = a[l];
        tre[pos].min = a[l];
        tre[pos].sum = a[l];
        return ;
    }

    int mid = l + r >> 1;
    build(l, mid, pos << 1);
    build(mid + 1, r, pos << 1 | 1);
    pushup(pos);
}

//区间上对数据进行修改
//注意：修改操作是为了对查询服务的，因此，修改不必要马上更新所有包含该点信息的节点上，只需要做上标记
//当查询查到这里，再更新也不迟。

void pushdown(int pos) {
    //把buff从上一层传递到下一层

    if (tre[pos].lazy_tag == 0) return ;
    //lazy-tag需要被传递到下一层，以保证传递信息的不丢失
    tre[pos << 1].lazy_tag += tre[pos].lazy_tag;
    tre[pos << 1 | 1].lazy_tag += tre[pos].lazy_tag;

    //sum,max,min传递
    tre[pos << 1].sum += tre[pos].lazy_tag * (tre[pos << 1].r - tre[pos << 1].l + 1);
    tre[pos << 1 | 1].sum += tre[pos].lazy_tag * (tre[pos << 1 | 1].r - tre[pos << 1 | 1].l + 1);

    //max,min
    tre[pos << 1].max += tre[pos].lazy_tag;
    tre[pos << 1 | 1].max += tre[pos].lazy_tag;

    tre[pos << 1].min += tre[pos].lazy_tag;
    tre[pos << 1 | 1].min += tre[pos].lazy_tag;

    //当传递完之后，pos的tag应该清零，表示当前区间没有需要传递下去的东西
    tre[pos].lazy_tag = 0;
}
void modify(int pos, int L, int R, int val) {
    if (tre[pos].r < L || tre[pos].l > R) return;
    if (tre[pos].l >= L && tre[pos].r <= R) {
        tre[pos].sum += (tre[pos].r - tre[pos].l + 1) * val;
        tre[pos].max += val;
        tre[pos].min += val;

        tre[pos].lazy_tag += val;

        return ;
    }

    /*
        当区间修改操作：需要递归到下一层时：也就是说半包含状态下
            需要先去往下更新lazy-tag，因为为了保证数据的准确性，不能在递归的修改的时候，上层还有没传递下来的数值

        所以这块需要从上往下进行tag的下放。

    */
   pushdown(pos);
   modify(pos << 1, L, R, val);
   modify(pos << 1 | 1, L, R , val);
   pushup(pos);
}
int queryMax(int pos, int L, int R) {
    if (tre[pos].r  < L || tre[pos].l > R) return 0;
    if (tre[pos].l >= L && tre[pos].r <= R) return tre[pos].max;

    pushdown(pos);
    return max(queryMax(pos << 1, L, R), queryMax(pos << 1 | 1, L, R));
}

int querySum(int pos, int L, int R) {
    if (tre[pos].r  < L || tre[pos].l > R) return 0;
    if (tre[pos].l >= L && tre[pos].r <= R) return tre[pos].sum;

    pushdown(pos);
    return querySum(pos << 1, L, R) + querySum(pos << 1 | 1, L, R);
}

//需要你修改的点
void update(int pos, int x, int val) { 
    if (tre[pos].l == tre[pos].r) {
        tre[pos].max = val;
        tre[pos].min = val; 
        tre[pos].sum = val;
        return ;
    }

    int mid = tre[pos].l + tre[pos].r >> 1;
    if (x <= mid) update(pos << 1, x, val);
    else update(pos << 1 | 1, x, val);

    pushup(pos);
}


int main(void)
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    build(1, n, 1);//l……n, 根节点从1开始
    int T;
    cin >> T;

    while (T--) {
        int op;
        cin >> op;

        if (op == 1) {
            int l, r, val;
            cin >> l >> r >> val;
            modify(1, l, r, val); 
        } else if (op == 2) {
            int l, r;
            cin >> l >> r;

            cout << queryMax(1, l, r) << '\n';
        } else if (op == 3){
            int l, r;
            cin >> l >> r;
            cout << querySum(1, l, r) << '\n';
        } else if (op == -1) {
            for (int i = 1; i <= n; i++) {
                cout << querySum(1, i, i) << ' ';
            }
            cout << '\n';
        }
    }

    return 0;
}
1 个赞