区间维护(树状数组)

问题描述:

题目描述


解题思路:

有关树状数组的基本知识这里就不再赘述,我们只需要知道他可以处理区间维护性的问题以及可修改的RMQ问题等,效率较高。

下面是有关线段树的操作

  • 单点修改
void update(int x,int k)
{
  for(;x<=n;x=x+(x&(-x))) t[x]+=k;
  //x位置的修改只对他的祖先造成影响,而x的祖先恰好是x+x&-x一路递增,因此直接修改x的祖先的值即可
  return ;
}
  • 区间查询
int sum(int x)
{
   int ans=0;
   for(;x;x-=x&-x) ans+=t[x];
   //将要查询的区间内所有的块都加起来,每个块之间的变化公式恰好是x-x&-x
   return ans;
}
  • 区间修改与查询

如果把整个区间修改的过程都像单点修改一样一路扫过去,那么树状数组就会退化为一个 Θ ( n l o g n ) \Theta (n log n) Θ(nlogn) 的算法,因此我们在面对这种带有区间修改的问题是,我们会尝试维护一个差分数组 d d d。

d i = a i − a i − 1 d_i=a_i-a_{i-1} di​=ai​−ai−1​

可以发现,差分与前缀和互为逆运算,若 f i f_i fi​ 表示差分数组 d 1 … d i d1…di d1…di 的和,那么 f i = a i f_i=a_i fi​=ai​,若 f i f_i fi​ 表示前缀和数组 s 1 … s i s1…si s1…si 的差分,那么 f i = a i f_i=a_i fi​=ai​ 。

根据差分数组由前缀和得到原数组的特性,我们发现,若在差分数组中的 l l l 位置修改一个数,将这个数 + k +k +k ,那么对于原数组来说 l l l 以后的所有数都会加上 k。若我们在 r r r 位置修改一个数,使得它减去 k,那么 r r r 之后的数在原数组中都会减去 k,因此,这区区两个单点修改就营造出了三个区间:

1 … l − 1 1…l-1 1…l−1 :不变
l … r l…r l…r : 全部加上k
r + 1 … n r+1…n r+1…n:不变

这不就实现了区间修改吗?效率飞快啊!

如果我们可以维护这么个差分数组那么原数组 a i a_i ai​ 的前缀和即为:

∑ i = 1 n a i = ∑ j = 1 i ∑ k = 1 j d k \sum_{i=1}^{n} a_i=\sum_{j=1}^{i}\sum_{k=1}^{j} d_k i=1∑n​ai​=j=1∑i​k=1∑j​dk​

不难发现, d 1 d_1 d1​ 在这条式子中会出现 n n n 次, d 2 d_2 d2​ 会出现 n − 1 n-1 n−1 次, … … … , d i d_i di​ 会出现 n − i + 1 n-i+1 n−i+1 次,因此:

∑ i = 1 n a i = ∑ j = 1 i ( d j ∗ n − d j ∗ ( j − 1 ) ) \sum_{i=1}^{n}a_i=\sum_{j=1}^{i} (d_j*n-d_j*(j-1)) i=1∑n​ai​=j=1∑i​(dj​∗n−dj​∗(j−1))

即:

∑ i = 1 n a i = n ∗ ∑ j = 1 i d j − ∑ j = 1 i d j ∗ ( j − 1 ) \sum_{i=1}^{n}a_i=n*\sum_{j=1}^{i} d_j-\sum_{j=1}^{i}d_j*(j-1) i=1∑n​ai​=n∗j=1∑i​dj​−j=1∑i​dj​∗(j−1)

因此,我们只需要用两个树状数组分别维护 d i d_i di​ 和 d i ∗ ( i − 1 ) d_i*(i-1) di​∗(i−1) 即可根据上面的公式求出区间和。

      if(pos==1)  //区间修改
      {
        //利用差分数组实现区间[c,b]加上d的操作
        cin>>d;
        update1(b,d);
        update1(c+1,-d);  //维护 d[i] 的树状数组
        update2(b,d*(b-1));
        update2(c+1,-d*c);  //维护 d[i]*(i-1) 的树状数组
      }
      else
      {
        long long s1,s2;
        s1=(b-1)*sum1(b-1)-sum2(b-1);
        s2=c*sum1(c)-sum2(c);
        //根据公式分别得出两段区间,区间相减求出任意区间
        cout<<s2-s1<<endl;
      }

CODE:

#include <bits/stdc++.h>
using namespace std;
long long n,m,pos,a[100010]={0},b,c,d;
long long t1[100010]={0},t2[100010]={0},o[100010]={0};
inline void update1(int x,int k)
{
  for(;x<=n;x+=x&-x) t1[x]+=k;
  return ;
}
inline void update2(int x,int k)
{
  for(;x<=n;x+=x&-x) t2[x]+=k;
  return ;
}
inline long long sum1(int x)
{
  long long s=0;
  for(;x;x-=x&-x) s+=t1[x];
  return s;
}
inline long long sum2(int x)
{
  long long s=0;
  for(;x;x-=x&-x) s+=t2[x];
  return s;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(register int i=1;i<=n;++i)
    {
      cin>>a[i];
      o[i]=a[i]-a[i-1];
    }
    for(int i=1;i<=n;i++) update1(i,o[i]),update2(i,o[i]*(i-1));
    for(register int i=1;i<=m;++i)
    {
      cin>>pos>>b>>c;
      if(pos==1)
      {
        cin>>d;
        update1(b,d);
        update1(c+1,-d);
        update2(b,d*(b-1));
        update2(c+1,-d*c);
      }
      else
      {
        long long s1,s2;
        s1=(b-1)*sum1(b-1)-sum2(b-1);
        s2=c*sum1(c)-sum2(c);
        cout<<s2-s1<<endl;
      }
    }
    return 0;
}
上一篇:百度吴甜做客央视《对话》:AI技术加持显著降低数字人生产成本


下一篇:高德发布最新 AI 引擎,汽车将是互联网地图的下一块战场