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....
Prefix arrays would help.
can you explain a little
https://usaco.guide/silver/prefix-sums?lang=cpp This is a nice resource.
but the answer will depend on x..isn't it?? how you gonna manipulate prefix sum array according to x??
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 "主席树".
yay!! great approach.... Thanks for the idea man...