In this ques What I can Think of is using a segment tree where each range will have f(x,k) sum for that range but problem that i am facing is how to store f(x,k) in node 1 approach is to have an array of size n for each node of segment tree where each index represent the count of time particular number in array occur in that range but this soln go upto O(n^2) 2 Is to calculate f(x,k) for each range but here problem is now how will i tackle update as for e.g. A[4] can occur in any range so update will also be a difficult job
Question approach not clear
At first, create the sum tree. Suppose that f(3)=1 f(4)=2 f(5)=3, and you need to add f(3)+f(4)+f(5) then at first u need to add 1 in range 3 to 5, then add 2 in range 3 to 5 and then add 3 in range 3 to 5. So, we get the sum in this range. Similarly, create a segment tree and for each i store the sum from i to i+k in the tree .When an update comes, then update the elements in range from current index of update(idx) to idx+k.