线段树模板

维护节点：

inline void uphold(int node)
{
    tr[node]=tr[node<<1]+tr[node<<1|1];//线段树求区间和
}

普通线段树

建树:

int a[N];
int tr[N<<2];//开四倍
void build(int node,int l,int r)
{
    if(l==r)
    {
        tr[node]=a[l];
        return;
    }
    int mid=(l+r)>>1;// (>>1) <=> (/2)
    build(node<<1, l, mid);
    build(node<<1|1, mid+1, r);
    uphold(node);//根据左右子树情况维护当前节点
}

单点修改：

void pmodify(int node,int l,int r,int x,int val)
{
    if(l==r)
    {
        tr[node]=val;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)
        pmodify(node<<1, l, mid,x,val);
    else pmodify(node<<1|1, mid+1, r,x,val);
    uphold(node);
}

下放 ：

int tag[N];
void lazy(int node,int l,int r)
{
    if(tag[node])
    {
        int mid=(l+r)>>1;
        tag[node<<1]+=tag[node];
        tag[node<<1|1]+=tag[node];
        tr[node<<1]+=tag[node]*(mid-l+1);
        tr[node<<1|1]+=tag[node]*(r-mid);
        tag[node]=0;
    }
}

区间修改：

void smodify(int node,int l,int r,int L,int R,int val)
{
    if(L<=l&&r<=R)
    {
        tr[node]+=val*(r-l+1);
        tag[node]+=val;
        return;
    }
    lazy(node,l,r);
    int mid=(l+r)>>1;
    int ret=0;
    if(L<=mid)smodify(node<<1,l,mid,L,R,val);
    if(R>=mid+1)smodify(node<<1|1,mid+1,r,L,R,val);
    uphold(node);
}

区间查询：

int query(int node,int l,int r,int L,int R)
{
    if(l>=L&&r<=R)
        return tr[node];
    lazy(node,l,r);
    int mid=(l+r)>>1;
    if(mid>=L)ret+=query(node<<1,l,mid,L,R);
    if(mid+1<=R)ret+=query(node<<1|1,mid+1,r,L,R);
    return ret;
}

模板：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=500010,M=100010;


int n,m;
int a[N];
int tr[N<<2];

void uphold(int node)
{
    tr[node]=tr[node<<1]+tr[node<<1|1];
}

void build(int node,int l,int r)
{
    if(l==r)
    {
        tr[node]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(node<<1, l, mid);
    build(node<<1|1, mid+1, r);
    uphold(node);
}

void pmodify(int node,int l,int r,int x,int val)
{
    if(l==r)
    {
        tr[node]=val;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)
        pmodify(node<<1, l, mid,x,val);
    else pmodify(node<<1|1, mid+1, r,x,val);
    uphold(node);
}

int tag[N];
void lazy(int node,int l,int r)
{
    if(tag[node])
    {
        int mid=(l+r)>>1;
        tag[node<<1]+=tag[node];
        tag[node<<1|1]+=tag[node];
        tr[node<<1]+=tag[node]*(mid-l+1);
        tr[node<<1|1]+=tag[node]*(r-mid);
        tag[node]=0;
    }
}

int query(int node,int l,int r,int L,int R)
{
    if(l>=L&&r<=R)
        return tr[node];
    lazy(node,l,r);
    int mid=(l+r)>>1;
    if(mid>=L)ret+=query(node<<1,l,mid,L,R);
    if(mid+1<=R)ret+=query(node<<1|1,mid+1,r,L,R);
    return ret;
}




void smodify(int node,int l,int r,int L,int R,int val)
{
    if(L<=l&&r<=R)
    {
        tr[node]+=val*(r-l+1);
        tag[node]+=val;
        return;
    }
    lazy(node,l,r);
    int mid=(l+r)>>1;
    int ret=0;
    if(L<=mid)smodify(node<<1,l,mid,L,R,val);
    if(R>=mid+1)smodify(node<<1|1,mid+1,r,L,R,val);
    uphold(node);
}



int main()
{
    /*Code*/
    return 0;
}

权值线段树

添加节点

void update(int node,int l,int r,int val)
{
    if(l==r)
    {
        tr[node]++;
        return;
    }
    int mid=(l+r)>>1;
    if(val<=mid)
        update(node<<1,l,mid,val);
    else update(node<<1|1,mid+1,r,val);
    uphold(node);
}

查询一段区间数出现次数总和

int find(int node,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)
        return tr[node];
    int mid=(l+r)>>1;
    int ret=0;
    if(L<=mid)
        ret+=find(node<<1,l,mid,L,R);
    if(R>=mid+1)
        ret+=find(node<<1|1,mid+1,r,L,R);
    return ret;
}

查询比x大的数有多少个(函数查大于等于)

int bquery(int node,int l,int r,int x)
{
    if(l==r)
        return tr[node];
    int mid=(l+r)>>1;
    if(x>mid)return bquery(node<<1|1,mid+1,r,x);
    else return tr[node<<1|1]+bquery(node<<1,l,mid,x);
}

bquery(1,1,n,x+1);

查询第k大的数值（不去重）

int fquery(int node,int l,int r,int k)
{
    if(l==r)return l;
    int mid=(l+r)>>1;
    if(k<=tr[node<<1])
        return fquery(node<<1,l,mid,k);
    else return fquery(node<<1,mid+1,r,k-tr[node<<1]);
}

模板

#include<iostream>
using namespace std;

int tr[1000];

inline void uphold(int node)
{
    tr[node]=tr[node<<1]+tr[node<<1|1];//Ï߶ÎÊ÷ÇóÇø¼äºÍ
}

void update(int node,int l,int r,int val)
{
    if(l==r)
    {
        tr[node]++;
        return;
    }
    int mid=(l+r)>>1;
    if(val<=mid)
        update(node<<1,l,mid,val);
    else update(node<<1|1,mid+1,r,val);
    uphold(node);
}

int find(int node,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)
        return tr[node];
    int mid=(l+r)>>1;
    int ret=0;
    if(L<=mid)
        ret+=find(node<<1,l,mid,L,R);
    if(R>=mid+1)
        ret+=find(node<<1|1,mid+1,r,L,R);
    return ret;
}

int bquery(int node,int l,int r,int x)
{
    if(l==r)
        return tr[node];
    int mid=(l+r)>>1;
    if(x>mid)return bquery(node<<1|1,mid+1,r,x);
    else return tr[node<<1|1]+bquery(node<<1,l,mid,x);
}

int fquery(int node,int l,int r,int k)
{
    if(l==r)return l;
    int mid=(l+r)>>1;
    if(k<=tr[node<<1])
        return fquery(node<<1,l,mid,k);
    else return fquery(node<<1,mid+1,r,k-tr[node<<1]);
}

int main()
{
    /*Code*/
    return 0;
}