一条线上有N个村庄。第i个村庄位于坐标X i处，有Pi个村民。回答Q问题。第i个查询的格式如下：给定整数Li和Ri，找到居住在坐标L和Ri之间的村庄的村民总数。C++

这是一个经典的线段树（Segment Tree）或区间查询的问题。在线性时间复杂度O(log N)内解决这个问题的关键在于构建一棵数据结构，它能支持高效的区间求和操作。以下是解决方案概述：

1. **数据结构**：创建一个大小为N的数组`tree`，其中`tree[i]`表示从0到`X[i)`这个区间的居民总和。线段树的每个节点存储的是其覆盖区间的居民总和。

2. **初始化**：对于每个村庄，将`tree[X[i]] += Pi`，因为第一个村庄的范围就是[0, X[1])，第二个村庄就是[X[1], X[2]),依此类推。

3. **查询过程**：对于给定的查询`(Li, Ri)`，你需要找出`tree[Ri] - tree[Li-1]`，这表示住在[L, R]之间所有村庄的总人数。注意，`tree[Li-1]`是一个技巧，因为我们想排除左边界不在查询范围内的部分。

4. **线段树操作**：线段树通过分治思想来加速查询。首先，计算区间的中间点，然后递归地在左半边和右半边进行相同的查询。每次查询只需要对树的高度进行log N次比较，因此整体时间复杂度是O(log N)。

struct SegTree {
    int n;
    vector<int> tree;

    void build(int arr[], int node = 0, int start = 0, int end = N) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2 * node, start, mid);
            build(arr, 2 * node + 1, mid + 1, end);
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }

    int query(int L, int R, int node = 0, int start = 0, int end = N) {
        if (L > end || R < start) return 0; // 如果区间不交，则返回0
        if (L <= start && R >= end) return tree[node]; // 区间完全包含在当前范围内
        int mid = (start + end) / 2;
        return query(L, R, 2 * node, start, mid) + query(L, R, 2 * node + 1, mid + 1, end);
    }
};