Hello Codeforces! I got jealous of [user:moemen_pro,2024-05-19] of writing educational bloggs and getting all the upvotes out there andd as an apprentice of the great [user:vjudge36,2024-05-19] 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!
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!
