How to solve this problem in time O(n log^k Cn) for some constant k? (or maybe it is impossible?)

Consider an array of size n with natural numbers not greater than C. I want to find three different elements in it (possibly their numbers will be equal) with maximal xor among all such triples.

For two elements the problem can be easily solved in time O(n log C), so I was thinking about this version. I haven't seen it before, neither on a contest nor on a training.

Is it possible to perform such operations with array in quasilinear total time (precalculations and queries)? 1. add a number x on a segment [l;r] 2. count the number of all elements in [l;r] which are <x If it is possible to solve this problem offline, then a new question arises: is it possible to solve it online with amortized O(log(n)^k) time per query (where k is a constant)?

I know that if a number is added to only one element (pos), then the problem can be solved in O(log(n)^2) time per query online using a segment tree with a treap in each node which consists of the elements of the segment which corresponds to the node. I also know that the given problem can be solved in O(sqrt(n)*log(n)) time per query (again, this works online) using sqrt-decomposition (we divide our array into sqrt(n) blocks of the size of sqrt(n), and then we maintain for each block it sorted and a modifier which is added to all the block's elements). But here the query time is too long.