基本模板(来自洛谷水题P4715题解区大佬yangrunze)

大佬的题解只针对了P4715这道水题,但也介绍了线段树的相关代码,我给整理了一下~算是初步了解吧!
之所以增改全是log的时间复杂度,本蒟认为二分思想功不可没~

#include <bits/stdc++.h>
using namespace std;
#define int long long
using pii = pair<int,int>;
struct node{
    int val;
    int id;
}a[100010],tree[100010];
node minn(node a ,node b){
    if(a.val<b.val) return a;
    else return b;
}
node maxx(node a ,node b){
    if(a.val<b.val) return b;
    else return a;
}
void build(int node,int ta,int nd)
{
    if(ta==nd) {tree[node]=a[nd];return;} 
    int mid = (ta+nd)>>1,ld=node*2,rd=node*2+1;
    build(ld,ta,mid);
    build(rd,mid+1,nd);
    tree[node]=maxx(tree[ld],tree[rd]);
    //tree[node].val=tree[rd].val+tree[ld].val;
}
void updata(int node,int ta,int nd,int x,int val)
{//更新数 
    if(nd==ta) {tree[node].val+=val;return;}
    int mid = (ta+nd)>>1,ld=node*2,rd=node*2+1;
    if(mid>=x&&x>=ta) updata(ld,ta,mid,x,val);//////////////范围!! 
    else updata(rd,mid+1,nd,x,val);
    //tree[node].val=tree[rd].val+tree[ld].val;////////////////更新!!! 
    tree[node]=maxx(tree[rd],tree[ld]);
}
int querysumormax(int node,int ta,int nd,int l,int r)
{
    if(ta>=l&&nd<=r) return tree[node].val;
    int mid = (ta+nd)>>1,ld=node*2,rd=node*2+1,sum=0,maxn=0;
    /*if(l<=mid) sum+=querysumormax(ld,ta,mid,l,r);
    if(mid<r) sum+=querysumormax(rd,mid+1,nd,l,r);*/
    if(l<=mid) maxn=max(maxn,querysumormax(ld,ta,mid,l,r));
    else maxn=max(maxn,querysumormax(rd,mid+1,nd,l,r));
    return maxn; 
    //return sum;
}
signed main()
{
    int n;cin >> n;
    for(int i = 1 ; i <= (1<<n) ; i++) cin >> a[i].val,a[i].id=i;
    build(1,1,1<<n);
    cout << tree[2].val << " " << tree[3].val << endl;
    updata(1,1,1<<n,2,90);
    cout << tree[2].val << " " << tree[3].val << endl;
    //cout << minn(tree[2],tree[3]).id << endl;
    cout << querysumormax(1,1,1<<n,5,8) << endl;
    cout << querysumormax(1,1,1<<n,1,4) << endl;
    return 0;
}