Nhận xét quan trọng: Tổng khoảng cách ~|x_i - X|~ nhỏ nhất khi ~X~ là median (trung vị) của tập hợp ~x_{l_k}..x_{r_k}~.

Ý tưởng:

1. Nén toạ độ:

   • Do toạ độ có thể lớn, ta cần nén các giá trị ~x_i~ để dễ xử lý với segment tree.

2. Xây dựng Persistent Segment Tree (PST):

   • Với mỗi ~i~, xây dựng version của PST chứa các phần tử ~x_1~ đến ~x_i~.
   • Mỗi node chứa:
     • ~count~: số phần tử.
     • ~sum~: tổng thực tế các giá trị (không phải giá trị đã nén).

3. Xử lý truy vấn ~[l, r]~:

   • Tìm median trong đoạn ~x_l~ đến ~x_r~ bằng cách truy cập ~PST_r~ và ~PST_{l-1}~.

   • Dùng PST để tính các thông tin sau:

     • median của mảng: ~val~.
     • ~cntL~: số phần tử ~\leq~ ~val~.
     • ~sumL~: tổng các phần tử ~\leq~ ~val~.
     • ~cntR = total - cntL~
     • ~sumR = totalSum - sumL~

   • Dựa vào các thông tin trên có thể tính được đáp án

Độ phức tạp: ~O(q \cdot \log n)~ sau khi xây dựng cây trong ~O(n \log n)~.