Problem Link : https://toph.co/p/another-update-query-problem
Solution Idea:
-
The main idea behind the solution of this problem is simplifying the equation. For a query operation we need the answer of this equation-
1A_l + (1+d)A_l+1 + (1+2d)A_l+2 + (1+3d)A_l+3 + … + (1+(r-l)d)A_r
Now let the query range l r is 1 3. and the given array is A=[a1,a2,a3,a4,…]
So our quation will be-
1*a1 + (1+d)*a2 + (1+2d)*a3 + (1+3d)*a4
= a1 + a2 + d*a2 + a3 + 2d*a3 + a4 + 3d*a4
= (a1+a2+a3+a4) + d*(a2+ 2*a3 + 3*a4)
Now We can see that first part of this equation is only sum query which can be done using a segment tree and for 2nd part we can use a trick. We can pree calculate the sequence like this-
1*a1 + 2*a2 + 3*a3 + 4*a4 + 5*a5 + 6*a6 + 7*a7 + ……
When we need the 2nd part of the equation we can use this equation. We can get the 2nd part of the equation from this equation by this way-
(2*a2 + 3*a3 + 4*a4)-(a2+a3+a4) = (a2+ 2*a3 + 3*a4).
Now the above equation is also only a sum equation. We can apply any range sum query or range sum update on this equation and the the first sum equation.
So if we store this two equation in two segment tree then we can perform range update or query on the segment tree and get any range sum query from the segment tree and using the equation we can answer each query of the problem correctly.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pii pair <int,int>
#define pll pair <long long,long long>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define db double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define sqr(x) (x)*(x)
#define D(x) cerr<<#x " = "<<(x)<<endl
#define VI vector <int>
#define DBG pf("Hi\n")
#define MOD 1000000007
#define CIN ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a) (int)a.size()
#define sf(a) scanf("%d",&a)
#define sfl(a) scanf("%lld",&a)
#define sff(a,b) scanf("%d %d",&a,&b)
#define sffl(a,b) scanf("%lld %lld",&a,&b)
#define sfff(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define RREP(i,a,b) for(int i=a;i>=b;i--)
#define TEST_CASE(t) for(int z=1;z<=t;z++)
#define PRINT_CASE printf("Case %d: ",z)
#define LINE_PRINT_CASE printf("Case %d:\n",z)
#define CASE_PRINT cout<<"Case "<<z<<": "
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define infinity (1<<28)
#define ull unsigned long long
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*------------------------------------------------*/
/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/
#define mx 100005
#define segment_tree int l=n*2,r=l+1,mid=(b+e)/2
struct data
{
ll sum, ssum, prop;
data()
{
sum=0,ssum=0,prop=0;
}
};
data tree[3*mx];
ll ara[mx];
ll interval_sum(ll b, ll e)
{
ll x=(e*(e+1))/2;
ll y=(b*(b-1))/2;
return (x-y+MOD)%MOD;
}
void push_down(int n, int b, int e)
{
if(tree[n].prop)
{
segment_tree;
tree[l].sum+=((mid-b+1)*tree[n].prop)%MOD;
tree[r].sum+=((e-mid)*tree[n].prop)%MOD;
tree[l].ssum+=(interval_sum(b,mid)*tree[n].prop)%MOD;
tree[r].ssum+=(interval_sum(mid+1,e)*tree[n].prop)%MOD;
tree[l].prop+=tree[n].prop%MOD;
tree[r].prop+=tree[n].prop%MOD;
tree[l].sum%=MOD;
tree[l].ssum%=MOD;
tree[l].prop%=MOD;
tree[r].sum%=MOD;
tree[r].ssum%=MOD;
tree[r].prop%=MOD;
tree[n].prop=0;
}
}
void init(int n, int b, int e)
{
if(b==e)
{
tree[n].sum=ara[b]%MOD;
tree[n].ssum=((ll)b*ara[b])%MOD;
tree[n].prop=0;
return;
}
segment_tree;
init(l,b,mid);
init(r,mid+1,e);
tree[n].sum=(tree[l].sum+tree[r].sum)%MOD;
tree[n].ssum=(tree[l].ssum+tree[r].ssum)%MOD;
tree[n].prop=0;
}
void update(int n, int b, int e, int i, int j, ll val)
{
if(b>j || e<i) return;
if(b>=i && e<=j)
{
tree[n].sum+=((ll)(e-b+1)*val)%MOD;
tree[n].ssum+=(interval_sum(b,e)*val)%MOD;
tree[n].prop+=val;
tree[n].sum%=MOD;
tree[n].ssum%=MOD;
tree[n].prop%=MOD;
return;
}
push_down(n,b,e);
segment_tree;
update(l,b,mid,i,j,val);
update(r,mid+1,e,i,j,val);
tree[n].ssum=(tree[l].ssum+tree[r].ssum)%MOD;
tree[n].sum=(tree[l].sum+tree[r].sum)%MOD;
}
data query(int n, int b, int e, int i, int j)
{
if(b>j || e<i) return data();
if(b>=i && e<=j)
return tree[n];
push_down(n,b,e);
segment_tree;
data p=query(l,b,mid,i,j);
data q=query(r,mid+1,e,i,j);
data ret;
ret.ssum=(p.ssum+q.ssum)%MOD;
ret.sum=(p.sum+q.sum)%MOD;
return ret;
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int t;
sf(t);
TEST_CASE(t)
{
int n,q;
sff(n,q);
loop1(i,n) sfl(ara[i]);
init(1,1,n);
LINE_PRINT_CASE;
while(q--)
{
int a,b,c,d;
sfff(a,b,c);
sf(d);
if(a==1)
{
update(1,1,n,b,c,d);
}
else
{
data ret=query(1,1,n,b,c);
ll sum=ret.sum;
ret=query(1,1,n,b+1,c);
ll ssum=(ret.ssum-(((ll)(b)*ret.sum)%MOD)+MOD)%MOD;
ssum*=(ll)d%MOD;
ssum%=MOD;
ll ans=(sum+ssum)%MOD;
printf("%lld\n",ans);
}
}
}
return 0;
}