权值线段树只是节点存的内容变成了权值，区间，区间和，区间数字个数等，和一般线段树的操作差别不大

但对于某些特定问题来说操作很简便，值域较大时一般会采用离散化（就只能离线了

可求区间第k大数，逆序对个数等

示例如图：

 //待添加

结构体存

struct node{    ll l, r, num;//区间范围，区间数字个数    ll s;        //区间和}tree[N*4];      //开4倍空间

 

建树

void build(ll l, ll r, ll now){    tree[now].l=l;    tree[now].r=r;    tree[now].s=0;    tree[now].num=0;    if(l==r)    {        return ;    }    ll mid=(l+r)>>1;    build(l,mid,now<<1);    build(mid+1,r,now<<1|1); //左右递归建树    return ;}

插入新点（根据不同问题修改

void update(ll pos, ll now) //pos为下标，b[pos]存值{    if(tree[now].l==tree[now].r)    {        tree[now].s+=b[pos];    //更新区间和，区间数字个数        tree[now].num++;        return ;    }    if(pos<=tree[now<<1].r) update(pos,now<<1);    else update(pos,now<<1|1);    tree[now].s=tree[now<<1].s+tree[now<<1|1].s;    tree[now].num=tree[now<<1].num+tree[now<<1|1].num;    return ;}

 查询（根据不同问题修改

ll query(ll now, ll k) //查询求和<=k的最大个数{    if(tree[now].s<=k) return tree[now].num;    if(tree[now].l==tree[now].r)        return min(tree[now].num, k/b[tree[now].l]);    if(k<=tree[now<<1].s) return query(now<<1,k);    else return tree[now<<1].num+query(now<<1|1,k-tree[now<<1].s);}

初始数据处理

for(i=1; i<=n; i++)    sc(a[i]), b[i]=a[i];sort(b+1,b+1+n);//需排序build(1,unique(b+1,b+n+1)-(b+1),1);//unique去重，初始建树ll pos=lower_bound(b+1,b+n+1,a[i])-b;//二分查找位置（ -(b+1)+1=-b  )update(pos,1);