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

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

#include <bits/stdc++.h>
using namespace std;
struct jgt{
    int val;
    int id;
};
jgt a[1888],tree[1888];
jgt minn(jgt a,jgt b)
{
    if(a.val<b.val) return a;
    else return b;
}
jgt maxx(jgt a,jgt b)
{
    if(a.val<b.val) return b;
    else return a;
}
void build(int node,int kai,int jie)
{
    if(kai==jie) {
        tree[node]=a[kai];
        return;
    }
    int mid = kai+jie>>1,rnode=2*node+1,lnode=2*node;
    build(lnode,kai,mid);
    build(rnode,mid+1,jie);
    tree[node]=maxx(tree[rnode],tree[lnode]);
}
void updata(int node,int kai,int jie,int id,int val)
{
    if(kai==jie) {
        tree[node].val+=val;
        return;
    }
    int mid = kai+jie>>1,rnode=2*node+1,lnode=2*node;
    if(id<=mid&&id>=kai) updata(lnode,kai,mid,id,val);
    else updata(rnode,mid+1,jie,id,val);
    tree[node].val+=val;
}
int query(int node,int kai,int jie,int l,int r)
{
    if(kai>=l&&r>=jie) return tree[node].val;
    int mid = kai+jie>>1,rnode=2*node+1,lnode=2*node,sum=0;
    if(mid>=l) sum+=query(lnode,kai,mid,l,r);
    if(mid<r) sum+=query(rnode,mid+1,jie,l,r);
    return sum;
}
int 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 << minn(tree[2],tree[3]).id << endl;
    updata(1,1,1<<n,2,1);
    cout << query(1,1,1<<n,2,3) << endl;
}