HDU6464 (权值线段树)-（查找区间第k1小于第k2小之间的和）

http://acm.hdu.edu.cn/showproblem.php?pid=6464

不理解先看博客：https://blog.csdn.net/g21glf/article/details/82986968

已知一开始有一个空序列，接下来有Q次操作，每次操作给出type、first和second三个值。当type为1时，意味着该操作属于第一种操作：往序列尾部添加first个second数。当type为2时，意味着该操作属于第二种操作：查询序列中第first小至第second小的数值之和（一共有(second - first + 1)个数被累加），并将结果对1000000007取模后输出。

#include<bits/stdc++.h>

using namespace std ;

#define ll long long

const ll inf=1e16;

const ll mod=1e9+;

const int maxn=1e5+;

ll sum[maxn*],val[maxn*];

int ls[maxn*],rs[maxn*];

int cnt;

void update(int &o , int l , int r , ll  k , ll num)///建树的过程

{

    if(!o)

    o=++cnt;

    sum[o]+=k;

    val[o]+=1LL*k*num;///作为记录全部小于k 的数的和

    val[o]%=mod;

    if(l==r) return ; //到底就返回

    int mid=(l+r)/;

    if(num<=mid)///在左子树

    update(ls[o] , l , mid , k , num);

    else

    update(rs[o] , mid+ , r , k , num);

}

ll query(int o , int l , int r , ll k)

{

    if(l==r) return 1LL*k*l%mod;///这里与单纯找第k小不一样o(原理差不多 ， 搜索到l 后 乘数量k)

    int mid=(l+r)/;

    ll ans=;

    if(k > sum[ls[o]]) /// 想找的数在右子树,前面有v个小于k的数 ， 则找右子树第k-v小的数

    {

        ans=(val[ls[o]] + query(rs[o] , mid+ , r , k-sum[ls[o]]))%mod;

    }

    else

        ans=query(ls[o],l,mid,k);

    return ans%mod;

}

int main()

{

    int Q,rt=;

    scanf("%d",&Q);

    while(Q--)

    {

        int op;

        ll l , r;

        scanf("%d%lld%lld",&op,&l,&r);

        if(op==) update(rt ,  ,1e9 , l , r);

        else

        {

            ///查找小于r的全部数和于 查找小于l-1的全部数和

            ll ans=(query(rt ,  , 1e9 , r) - query(rt,,1e9 , l-) + mod)%mod;

            printf("%lld\n",ans);

        }

    }

}