LCA

最近公共祖先

建议背诵（

///https://www.luogu.com.cn/problem/P3379

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
int n,m,s;
int dep[maxn];
int f[maxn][20];
int maxi;
vector<int> E[maxn];
//每个节点有一个存入的是他的父节点，遍历的时候遇到那个直接跳过，剩下的就都是子节点了

void init(){
    memset(dep,0,sizeof(dep));
    memset(f,0,sizeof(f));
}
void dfs(int x,int pre){
    dep[x]=dep[pre]+1;
    f[x][0]=pre;
    for(int i=1;(1<<i)<=n;i++){
        f[x][i] = f[ f[x][i-1] ][ i-1 ];
        maxi=i;
    }
    for(int i=0;i<E[x].size();i++){
        if(E[x][i]==pre) continue;
        dfs(E[x][i],x);
    }
}

int up(int x,int d){//x向上走d步
    int ret=x;
    //真不行，感觉要背过
    for(int i=0;(1<<i)<=n;i++){
        if(((1<<i)&d)!=0){
            ret=f[ret][i];
        }
    }
    return ret;
}

int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    x=up(x,dep[x]-dep[y]);
    if(x==y) return x;
    for(int i=maxi;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
//    cout<<'x'<<x<<"  y"<<y<<endl;
//    cout<<"xpre"<<f[x][0]<<" ypre"<<f[y][0]<<endl;
    return f[x][0];
}

int main(){
    init();
    cin>>n>>m>>s;
    for(int i=0;i<n-1;i++){
        int x,y;
        cin>>x>>y;
        E[x].push_back(y);
        E[y].push_back(x);
    }
    //dfs
    for(int i=0;i<E[s].size();i++){
        dfs(E[s][i],s);
    }
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        cout<<lca(a,b)<<endl;
    }
}

SegmentTree

线段树

记得多做题练练啊

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
typedef long long ll;
ll tree[maxn*4],lazy[maxn*4];
int n,q;
void push_up(int rt){
    tree[rt]=tree[rt*2]+tree[rt*2+1];
}
void push_down(int l,int r,int rt){
    int mid=(l+r)/2;
    if(lazy[rt]==0 || l==r) return;
    tree[rt*2]+=lazy[rt]*(mid-l+1);
    tree[rt*2+1]+=lazy[rt]*(r-mid);
    lazy[rt*2]+=lazy[rt];
    lazy[rt*2+1]+=lazy[rt];
    lazy[rt]=0;
}
void build(int l,int r,int rt){
    if(l==r){
        cin>>tree[rt];
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,rt*2);
    build(mid+1,r,rt*2+1);
    push_up(rt);
}
//void modify(int l,int r,int rt,int x,int add){
//    if(l==r){
//        tree[rt]+=add;
//        return;
//    }
//    int mid=(l+r)/2;
//    if(x<=mid)  modify(l,mid,rt*2,x,add);
//    else modify(mid+1,r,rt*2+1,x,add);
//    push_up(rt);
//}
void init(){
    memset(tree,0,sizeof(tree));
    memset(lazy,0,sizeof((lazy)));
}
void modify(int l,int r,int rt,int L,int R,ll add){
    if(l>=L && r<=R){
        tree[rt]+=(r-l+1)*add;
        lazy[rt]+=add;
        return;
    }
    push_down(l,r,rt);
    int mid=(l+r)/2;
    if(mid>=L)  modify(l,mid,rt*2,L,R,add);
    if(mid+1<=R)    modify(mid+1,r,rt*2+1,L,R,add);
    push_up(rt);
}
//    ll query(int l,int r,int rt,int L,int R){
//    if(l>=L && r<=R){
//        return tree[rt];
//    }
//    int mid=(l+r)/2;
//    ll ret=0;
//    if(mid>=L)  ret+=query(l,mid,rt*2,L,R);
//    if(mid+1<=R)    ret+=query(mid+1,r,rt*2+1,L,R);
//    return ret;
//}
ll query(int l,int r,int rt,int L,int R){
    if(l>=L && r<=R){
        return tree[rt];
    }
    int mid=(l+r)/2;
    ll ret=0;
    push_down(l,r,rt);
    if(mid>=L)  ret+=query(l,mid,rt*2,L,R);
    if(mid+1<=R)    ret+=query(mid+1,r,rt*2+1,L,R);
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>q;
    init();
    build(1,n,1);
    for(int i=1;i<=q;++i){
        int x,y,z;
        cin>>x>>y>>z;
        if(x==1){
            int temp;
            cin>>temp;
            modify(1,n,1,y,z,temp);
        }else{
            cout<<query(1,n,1,y,z)<<endl;
        }
    }
}