KiAsaGibona's blog

Help To Debug CodeForces #179 Div2 C-Greg and Array
By KiAsaGibona, 10 years ago, In English

Hi everyone, Please help me finding out the mistake I did in Greg and Array. I am using Binary Indexed Tree to solve this problem and Implemented the idea of this site (main idea is given below, however, please visit the site for complete documentation of the algorithm)..

My complete code is Available In Pastebin

Algorithm that I tried to Implement:

update(ft, p, v):
    for (; p <= N; p += p&(-p))
        ft[p] += v 	 
 
# Add v to A[a...b] 
update(a, b, v): 	
    update(B1, a, v) 	
    update(B1, b + 1, -v) 	
    update(B2, a, v * (a-1)) 	
    update(B2, b + 1, -v * b) 	 
 
query(ft, b): 	
    sum = 0 	
    for(; b > 0; b -= b&(-b))
        sum += ft[b]
    return sum
 
# Return sum A[1...b]
query(b):
    return query(B1, b) * b - query(B2, b)
 
# Return sum A[a...b]
query(a, b):
    return query(b) - query(a-1)
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why are you even using BIT...? The problem is much easier than that.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I know it's a normal simulation problem. But I am trying to learn range update and range query of Binary Indexed Tree.

    → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

This problem can be done in O(m+n) you don't need BIT

→ Reply