Suppose given array is a[0..N-1],
Define s[k]=a[0]+a[1]+...+a[k], k=0..N-1
The problem asks to implement 2 operations:
1) increase a[p],a[p+1]..a[q] by v
2) query a[p]+a[p+1]+..+a[q]
Define array b[0..N-1] and sb[0..N-1]:
b[0] = a[0],
b[k] = a[k] - a[k-1] for k>0,
sb[k] = b[0]+b[1]+..+b[k].
Then a[k] = b[0] + b[1] + .. + b[k]
s[k] = b[0] + (b[0]+b[1]) + .. + (b[0]+b[1]+..+b[k])
= (k+1)b[0] + k*b[1] + .. + b[k]
= (k+1)(b[0]+b[1]+..+b[k]) - (0*b[0]+1*b[1]+..+k*b[k])
Define c[k] = k * b[k] for k=0..N-1, and sc[k] = c[0]+c[1]+..+c[k].
Then s[k] = (k+1)*sb[k] - sc[k]
(b[k],sb[k]) and (c[k],sc[k]) can be maintained by 2 BITs
1) is archived by updating b[p], b[q+1], c[p] and c[q+1]
2) can be easily computed after query sb[k] and sc[k] (k=p-1,q)
2013/3/13 Aman Jain <[email protected]>
> Here in this code given below,
> Horrible is solved using 2 BIT(binary indexed trees)
> Can Someone please explain the Logic of the program or suggest other way
> to do the same ques using BIT
> problem here coming is here range query and range updation both
> simultaneously which is difficult with BIT.
> #include <cstdio>
> #include <cstring>
>
> using namespace std;
>
> long long bit1[100002],bit2[100002];
>
> void update(long long bit[], int idx, long long val){
> for(int x = idx;x <= 100001;x += x & -x)
> bit[x] += val;
> }
>
> long long query(long long bit[], int idx){
> long long ret = 0;
>
> for(int x = idx;x > 0;x -= x & -x)
> ret += bit[x];
>
> return ret;
> }
>
> int main(){
> int T,N,Q;
>
> scanf("%d",&T);
>
> while(T--){
> scanf("%d %d",&N,&Q);
>
> memset(bit1,0,sizeof bit1);
> memset(bit2,0,sizeof bit2);
>
> for(int i = 0,op,l,r,v;i < Q;++i){
> scanf("%d %d %d",&op,&l,&r);
>
> if(op == 0){
> scanf("%d",&v);
>
> update(bit1,l,v); update(bit1,r + 1,-v);
> update(bit2,l,-(long long)v * (l - 1)); update(bit2,r +
> 1,(long long)v * r);
> }else{
> printf("%lld\n",query(bit1,r) * r + query(bit2,r) -
> query(bit1,l - 1) * (l - 1) - query(bit2,l - 1));
> }
> }
> }
>
> return 0;
> }
>
>
> On Tue, Feb 26, 2013 at 3:13 PM, dheeraj hasija <
> [email protected]> wrote:
>
>> you can have this code for better understanding
>>
>> #include<stdio.h>
>>
>> long long v[500000];
>> long long a[500000];
>>
>>
>> inline long long getvalue( int index, int low, int high)
>> {
>> return a[index] + (high-low+1)*v[index];
>> }
>>
>> long long update( long long index, long long down, long long up, long
>> long low, long long high,long long value)
>> {
>> long long mid = (low+high)/2;
>>
>>
>>
>> if( down <= low && high <= up)
>> {v[index] += value;
>>
>> return 0;
>> }
>>
>> if(low> up || high < down)
>> return 0;
>>
>> v[2*index] += v[index];
>> v[2*index+1] += v[index];
>> v[index] = 0;
>>
>> update( 2*index, down,up, low,mid,value);
>> update(2*index+1 , down,up, mid+1, high,value);
>>
>>
>>
>> a[index] = getvalue(2*index, low, mid) + getvalue(2*index+1 ,
>> mid+1,high);
>> return 0;
>>
>>
>> }
>>
>>
>>
>> long long query( long long index, long long down, long long up, long long
>> low, long long high)
>> {
>>
>> //printf("%lld %lld %lld %lld",low,high,up,down);
>>
>> long long mid;
>> mid = (low+high)/2;
>>
>>
>>
>>
>> if( down <= low && high<=up)
>> return a[index] + v[index]*( high-low+1);
>>
>> if( low > up || high < down)
>> return 0;
>>
>>
>> v[2*index] += v[index];
>> v[2*index+1] += v[index];
>>
>>
>>
>>
>> a[index] = getvalue(2*index, low, mid) + getvalue(2*index+1 ,
>> mid+1,high);
>>
>>
>>
>> v[index] =0;
>>
>> return query( 2*index,down,up, low, mid)+query(2*index+1, down,up,
>> mid+1, high);
>>
>>
>>
>>
>> }
>>
>>
>>
>>
>> int main()
>> {
>> long long t,n,p,quer,vr,val,i,q;
>>
>>
>> scanf("%lld",&t);
>>
>> while(t--)
>> {
>> scanf("%lld%lld",&n,&quer);
>>
>> for(i=0;i<=4*n;i++)
>> a[i] =0,v[i] =0;
>>
>>
>> while(quer--)
>> {
>> // for(i=1;i<8;i++)
>> //printf("%lld ",a[i]);
>> //printf("\n");
>>
>> scanf("%lld%lld%lld",&vr,&p,&q);
>> if(!vr)
>> {scanf("%lld",&val);
>> update( 1,p,q,1,n,val);
>> }
>> else
>> printf("%lld\n",query( 1, p, q, 1, n));
>> }
>>
>> //printf("bye");
>> }
>>
>> return 0;
>> }
>>
>>
>>
>> On Tue, Feb 26, 2013 at 12:24 PM, emmy <[email protected]> wrote:
>>
>>> Problem statement <http://www.spoj.com/problems/HORRIBLE/>
>>>
>>> Here <http://ideone.com/NhDuYo> is my code. I am using segment trees +
>>> Lazy propagation. Please help me figure out my mistake.
>>> I am getting a WA
>>>
>>> Note:
>>> invariant : l <= p <=q <= r
>>>
>>> l and r are the limits of that node
>>> p and q is the query range.
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to [email protected].
>>> For more options, visit https://groups.google.com/groups/opt_out.
>>>
>>>
>>>
>>
>>
>>
>> --
>> *Dheeraj Hasija*
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to [email protected].
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
__________________________________________________
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
