给定一个长度为 $n$ 的数组 $a$ 以及 $q$ 组询问，每组询问有三个数 $l,r,x$，回答在数组 $a$ 的区间 $[l,r]$ 之间是否存在一些元素的和恰好为 $x$。

假设 $1 \leq a_i \leq 10^9$。

（1）当 $1 \leq n \leq 10^3$，$1 \leq q \leq 5 \times 10^5$ 时，最简单的做法是什么？

（2）在第（1）问的基础上，如果用数组 $a$ 构造一棵线段树，且保证 $[l,r]$ 表示的区间是树上的一个节点表示的区间，此时最简单的做法的时间复杂度可以达到多少？