Can you provide constraints, or a link to the actual problem?

Also, can you tell us what exactly you are storing in the segment tree that it gives memory limit exceeded.

Here is what I think you are asking : Each query is of the form **L R K** and you have to find the largest index i, L \leq i \leq R such that a[L], A[L+1], A[L+2] \cdots A[i] are all divisible by K.

**An O(\log^2 n) per query solution :**

Create a segment tree and in each node store the **gcd** of its segment ( This should not give Memory Limit Exceeded since we are storing just one integer per node and there are O(n) nodes ).

If a number divides all elements of a segment, it divides the **gcd** of those elements.

We can get the gcd of a segment in O(\log n) using this. Just binary search for the largest i.

**An O(\log n) per query solution:**

The range [L,R] would be divided into at most \log(n) segments by the segment tree. Find the leftmost segment whose gcd is not divisible by K ( You can have your query function return this node ). If there is no such node, then i is R.

Otherwise, i+1 ( such that i is as described above ) has to lie in this segment. Then, if the left child of this node has a gcd divisible by K, then i+1 must lie in the right child of this segment. Otherwise, i+1 must lie in the left child. Continue like this until the segment has length 1.

Personally, if the constraints allow, I would prefer the O(\log^2 n) per query solution since it is much easier to code.