树状数组

题意：

分析：

这两天一直在学习树状数组，但做题的时候总是有些摸不到头脑。不知道要在何处构造树状数组？
又要用树状数组表示什么？

通过这题，我来总结一下吧。
这题中我们要求sum(l,r)[ai<=x]
很明显直接去往区间里看是不行的，因为我们无法区分出ai<=x
那我们简化一下问题吧。
求sum(1,n)[ai<=x]
这该怎么求呢？我们不可能每一次查询时都遍历整个数组吧。
很简单我们就会想到，我们对数组从小到大排序，再对查询从小到大排序。
然后遍历数组，并且计数，然后如果发现现在遍历的数组元素已经大于查询栈顶的查询值时，
那么这次查询的结果就是计数数！
这是很简单就能想到的。

与之不同的仅仅是这里加上了区间。
那我们遍历数组时，将当前元素原本所在的索引上+1，然后在查询时再用树状数组计数不就好了！！

代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
struct lrk { int l, r, k, num; bool operator<(const lrk& t1) { return k < t1.k; } };
const int mx = 1e5 + 100;
int n, m;
pii a[mx];
lrk b[mx];
int BIT[mx];
ll ans[mx];

void renew(int id) {
    for (;id <= n;id += (id & -id))BIT[id]++;
}

ll quiry(int id) {
    if (id == 0)return 0;
    ll res = 0;
    for (;id;id -= (id & -id))res += BIT[id];
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1;i <= n;i++)cin >> a[i].first, a[i].second = i;
    for (int i = 1;i <= m;i++)cin >> b[i].l >> b[i].r >> b[i].k, b[i].num = i;
    sort(a + 1, a + 1 + n);sort(b + 1, b + 1 + m);
    int i = 1;int j = 1;
    while (j <= m) {
        if (b[j].k < a[i].first || i == n + 1) {
            ans[b[j].num] = quiry(b[j].r) - quiry(b[j].l - 1);
            j++;
        }
        else {
            renew(a[i].second);
            i++;
        }
    }
    for (int i = 1;i <= m;i++)cout << ans[i] << endl;
}

从上述分析中我们发现，树状数组主要是解决一个动态的区间问题。
动态区间问题！动态区间问题！动态区间问题！
我认为这是动态数组的特征！
也就是说我们若想用树状数组解题，很大可能会把他转化为一个动态的区间问题！
但是，树状数组是工具，就像二分一样。对于一个问题，我们不可能一开始就想到要用动态数组去解决。
那突破点在哪里呢？
我认为在动态上！
如同上题，排序后动态处理让我们解决了约束条件<=k
动态处理可以帮助我们解决一些约束条件！！！！
我认为这是关键!

如果有大神看到，希望能指点一二，传点心得