vjudge38's blog

By vjudge38, history, 4 weeks ago, In English

Hello Codeforces! I got jealous of moemen_pro of writing educational bloggs and getting all the upvotes out there andd as an apprentice of the great vjudge36 I decided to write a blog abput a new topic i created on my own!!!! Let's say we have an array $$$a$$$ of length $$$n$$$ and we have $$$q$$$ queries of the form "what is the sum of elements in the range $$$[l,r]$$$ ????????????? Well of course the anive way is to build a sqet decpmpoistion but it is way too slow. Let's tiko of something faster. YeS! Lqoopijng!!! but how to loop ? it's $$$O(n)$$$. Well here wa can decompose the array into negative sized imaginary blocks, so we can loop through them in $$$O(inq)$$$ where $$$i=\sqrt{-1}$$$. Now is this complexity really faster? Well it's imaginary so it doesn't even exist!!!!!!!!!!!! Code:

#include <bits/stdc++.h>
using namespace std;
int main(){
   int n,q;
   cin>>n>>q;
   int a[n],q,b[-n];
   for (int i=1;i<=n;i++) b[-i]=a[i];
   while (q--){
      int l,r,ans=0;cin>>l>>r;
      for (int i=r;i>=l;i--) ans+=b[i];
      cout<<ans<<endl;
   }return 0;
}

You can also update using this technique simply by updating the array $$$b$$$ and can answer many types of queriers.

pLEASE upvote for more lbof slile this!

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by vjudge38 (previous revision, new revision, compare).