### shivam_360's blog

By shivam_360, history, 17 months ago,

we are given with an array of n integers n<=10^5 , we need to answer q queries q<=10^5 , in each query we are given with l,r and an integer x, for each query we need to answer the summation of |a[i]-x| for all i>=l && i<=r (summation of absolute difference of each number with x in range l and r)..as constraints are big we need to solve each query in less than n... Can anyone suggest some approach with some thought process....

• +3

 » 17 months ago, # |   0 Prefix arrays would help.
•  » » 17 months ago, # ^ |   0 can you explain a little
•  » » » 17 months ago, # ^ |   0 https://usaco.guide/silver/prefix-sums?lang=cpp This is a nice resource.
•  » » » » 17 months ago, # ^ |   0 but the answer will depend on x..isn't it?? how you gonna manipulate prefix sum array according to x??
 » 17 months ago, # | ← Rev. 7 →   +5 If we can answer the following questions quickly, we will succeed:(1) How many numbers $n$ in $\{a[l], ..., a[r]\}$ are less or equal than $x$?(2) What is the sum of numbers of $n$ such that $n \in \{a[l], ..., a[r]\}$ and $n \leq x$?These two questions can be answered using a persistent segment tree, also known as the "主席树".
•  » » 17 months ago, # ^ |   +1 yay!! great approach.... Thanks for the idea man...