Binary indexed tree

general
, ,
1

#include
void scan(int &n )
{
n=0;
int ch=getchar();
while( ch < ‘0’ || ch > ‘9’ )
ch=getchar();
while( ch >= ‘0’ && ch <= ‘9’ )
n = (n<<3)+(n<<1) + ch-‘0’, ch=getchar();
}
int n,q,ft[100003],pivot,l,r,i;
void query(int a,int b)
{
for(;a<=n;a+=a&(-a))
ft[a]+=b;
}
void range(int a,int b,int c)
{
query(a,c);
query(b+1,-c);
}
int retreive(int a)
{
int sum=0;
while(a)
{
sum+=ft[a];
a-=a&(-a);
}
return sum;
}
main()
{
int temp,count;
for(i=0;i<100002;i++)
ft[i]=0;
scan(n);
scan(q);
while(q–)
{ count=0;
scan(pivot);
if(pivot)
{
scan(l);
scan®;
l++;r++;
for(i=l;i<=r;i++)
{
temp=retreive(i);
if(temp%2)
count++;
}
printf("%d\n",count);

                  }
                  else
                  {
                    scan(l);
                    scan(r);
                    l++;r++;
                    range(l,r,1);
                  }
                  
  }
  return 0;
}

the followintg code gives TLE in ques FLIPCOIN… i am using bit for range updates … but O(n)… for retreiving … how to modify it… http://www.codechef.com/problems/FLIPCOIN

2

I don’t think you can can do both O(logN) with a Fenwick tree. Just use Segment Tree with lazy propagation for AC.

1 Like