离散化

特征：操作次数不多，相关点不多

  • 离线与在线
    离线：先存操作/询问后执行操作
    在线：输入一次数据执行一次操作
  1. 找出相关点并存下/收集所有需要离散化的值
  2. 将相关点排序并去重
  3. 大点(小点)到小点(大点)的映射
    通过二分实现大点映射到小点（根据值找位置->二分），通过离散化数组实现小点映射到大点
  4. 将操作全部转化为小点上
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*输入：
n 个添加操作，每个操作包含一个坐标 x 和一个权重 w。
q 个查询操作，每个查询包含一个区间 [l, r]。
目标：
对每个查询，计算区间 [l, r] 内所有 x 的权重和。*/
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 9;
using ll = long long;
int a[N];
vector<int> LS;
struct op
{
    int a, b;
} add[N], que[N];
//离散化映射
int getindex(int x)
{
    return lower_bound(LS.begin(), LS.end(), x) - LS.begin() + 1;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;
    //找出相关点并存下/收集所有需要离散化的值
    for (int i = 1; i <= n;++i)
    {
        int w, x;
        cin >> w >> x;
        LS.push_back(w);
        add[i] = {w, x};
    }
    for (int i = 1; i <= q;++i)
    {
        int l, r;
        cin >> l >> r;
        LS.push_back(l), LS.push_back(r);
        que[i] = {l, r};
    }
    //排序和去重
    sort(LS.begin(), LS.end());
    LS.erase(unique(LS.begin(), LS.end()), LS.end());
    //将操作全部转化为小点上
    for (int i = 1; i <= n;i++)
        a[getindex(add[i].a)] += add[i].b;
    for (int i = 1;i<=LS.size();i++)
        a[i] += a[i - 1];
    for (int i = 1; i <= q;i++)
    {
        int l = getindex(que[i].a), r = getindex(que[i].b);
        cout << a[r] - a[l - 1]<<'\n';
    }
    return 0;
}

树状数组

lowbit()的实现，树状数组的初始化

单点修改