Querying the probability of choosing even or odd elements in a subarray
Well, first you should properly format your code. Readability means maintainability, and fewer bugs.

Try to avoid type-conversions and casts. They are danger-points, and if you use a decent warning-level, your compiler should warn about potentially dangerous type-conversions at least.
In gcd() you use int everywhere but once, where you use unsigned int. Fix that.

You have three query-types, and you seem to desperately want to make them share code. Don't do that! Branch-misprediction is expensive, and moving work out of inner loops is always a win. Hopefully, your compiler will do it for you, so the compiled code does not suffer from your choice like the source code does.

Take a look at which compound-assignment-operators are available. They make assignments more readable and concise.

Try to declare your variables in the smallest scope you can for better readability. Even if you insist on strict C89 with GCC builtins, you can go further.

Don't assume success! scanf() and malloc() can fail, so check for it.

Don't cast the result of malloc(). It's unnecessary and error-prone.

Normalize the range early-on for ease of use. A pointer and a length are sufficient unless you need the position in the surrounding array, and you don't.


You might want to experiment with using a bit-vector, or representing the array as spans of odd / even numbers.