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 <dheerajhasija1...@gmail.com
> 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 <foramlakh...@gmail.com> 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 algogeeks+unsubscr...@googlegroups.com.
>> 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 algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
