区间维护（树状数组）

2024-01-03 08:47:41

问题描述：

解题思路：

有关树状数组的基本知识这里就不再赘述，我们只需要知道他可以处理区间维护性的问题以及可修改的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∑nai=j=1∑ik=1∑jdk

不难发现， 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∑nai=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∑nai=n∗j=1∑idj−j=1∑idj∗(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;
}

码农公寓

问题描述：

解题思路：

CODE:

相关文章