HORRIBLE : TLE Even With Binary Indexed Trees (BIT) SPOJ Horrible Queries

general
, , ,
1

The Following is a Piece of Code From my SPOJ Submission ,From What i Understand of The Question , It Should be Very Easy and BIT Should BE The Ideal Data Structure To be used here , But Sill i am Getting Time Limit Exceeded on my Submissions …

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define MAX 100001
typedef long long int ll;
ll BIT[MAX];
void update(ll n,ll val,ll N)
{
        for(;n<=N;BIT[n]+=val,n+=n&-n);
}
ll read(ll n)
{
    ll sum=0;
    for(;n;sum+=BIT[n],n-=n&-n);
    return sum;
}
int main()
{
    ll t;
    scanf("%lld",&t);

    while(t--)
    {
        memset(BIT,0,sizeof BIT);
        ll n,c;
        scanf("%lld %lld",&n,&c);
        ll ch,p,q,v;
        while(c--){
        scanf("%lld",&ch);
        if(ch==0)
        {
            scanf("%lld %lld %lld",&p,&q,&v);
            for(ll k=p;k<=q;k++)
            {
                update(k,v,n); // Passing Size of Array as well So as to Not Iterate Through all 10001 All
            }

        }
        else
        {
            scanf("%lld %lld",&p,&q);
            printf("%lld",read(q)-read(p-1));// Return Sum of Range From p to q
        }
        }
    }
}**
2

Hint: You need to use two BITs for this problem to reduce number of computations while performing Range Query and Range Update.

1 Like
3

I Didn’t Get your Answer ??

4

You may try using segment trees