Ehsan_sShuvo's blog

Explanation need!
By Ehsan_sShuvo, history, 8 years ago, In English

I have tried my level best to understand this problem.Could anyone else please explain me how i solve this problem?

Note: I know Binary Indexed tree and want to solve this problem by this algorithm.Google search couldn't make a sense for myself to solve this problem.Everywhere,i saw,sort query according to it's value 'k'.And suggestion was that sort your given array also..But,i failed to get that!Pure explanation needed!

Thanks in advance!

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hi, I just solved your problem.

  • Sort the array in increasing order of values(index attached to values)
  • Make another array with all values initialised to 0. This means initially no value is present at any index. When we will add some value to this array, we will put 1 at its corresponding index.
  • Start processing queries in decreasing order of K
  • Now for current K see how many numbers in the old sorted array are greater than K(by traversing from back and keep a top variable so that in future u don't start again from last but from this top value as all values greater than this will be already present in the new array). At all those indices(which were attahced with their corresponding values as I said in first step) update the value in new array from 0 to 1(This means they are now present in new arrray). Then query sum over range l to r. Both this operation can be done with Binary-Indexed-Tree. Remember that we will call update function for an index exactly one time so overall update complexity will be n*logn and query will be q*2*logn.

Here is my Accepted code

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it -10 Vote: I do not like it

    Don't care about this gray newbie, just enjoy my standup

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

      which language you have written in your blog post!Google translator is my only one friend for this purpose!

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

        Ignore him. He is a spammer.

        → Reply