Statements are something like so: Given 1 ≤ n ≤ 10⁵ and an array of n integers 1 ≤ a_i ≤ n,

Needed answer "NO" if this is not possible to divide the array into two groups of same sum or answer "YES" and print all numbers in first group and second group.

The task sounds similar to knapsack problem, and I know only the greedy approach this problem, but I know that this should be possible (according to problem editorial) to solve it with with knapsack approach.

Link to Editorial (Russian only) and to problem (Task C) Statements (Also russian only)

I hope you will be able to help me. :]

I mean proven things like comparison sort can't have an asymptotic better than N * log(N). I haven't ever heard about other similar cases. Is there anyone who knows?

UPD: probably I did not describe the question properly enough, although zxqfl gave an answer I expected to get. I have meant that we have some sort of problem with strict restrictions, for example finding a minimal path from S to T in a graph with 1 ≤ w(e) ≤ 10⁹ integer length of all edges and this is proven that this task can not be solved faster than in O(M * logN) or something like that. (Not exactly saying I know how to prove this, just giving an example)

Given array V of integers.

Need to answer query of two types:

1. Given L, R, A, B, need to count how many A ≤ j ≤ B are so that L ≤ V_j ≤ R

2. Given i and X, V_i = X

Someone told me that this is impossible task in O(log n).

Is this true? Can anyone prove me that or prove it being wrong?

It seems to be complicated. If anyone has any idea how to solve it faster than O(log² n) I'd also like to hear that. O(log n * log max) is also pretty obvious solution (max is maximum value that can be stored in array)