Java教程

区间修改区间求和

本文主要是介绍区间修改区间求和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

存个树状数组的板子省的每次都抄别人

struct sgt{
  ll c1[N],c2[N]; 
  inline void update(ll x,ll k)
  {
    ll i=x;
    while(x<=n)
    {
        c1[x]+=k;
        c2[x]+=i*k;
        x+=x&-x;
    }
    return;
  }
  inline ll sum(ll x)
  {
    ll ans=0;
    ll i=x;
    while(x>0)
    {
        ans+=c1[x]*(i+1);
        ans-=c2[x];
        x-=x&-x;
    }
    return ans;
  }
   inline void change(int x,int y,ll z)
   {
  //     cerr<<x<<" "<<y<<endl;
      update(x,z);
      update(y+1,-z);
   }
   ll query(int x)
   {
      return sum(x)-sum(x-1);
   }
}S; 

 

这篇关于区间修改区间求和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!