我需要一个支持三种操作的范围最小查询数据结构:
- 使用数组 A[n] 初始化
- 更新(i,j,v) - 将 v 添加到范围 A[i]...A[j] 中的所有元素
- 查询 (i,j) - 从范围 A[i]...A[j] 中找到最小元素
更新和查询都必须及时运行,O(log n)
并且结构必须占用O(n)
空间。
我需要一个支持三种操作的范围最小查询数据结构:
- 使用数组 A[n] 初始化
- 更新(i,j,v) - 将 v 添加到范围 A[i]...A[j] 中的所有元素
- 查询 (i,j) - 从范围 A[i]...A[j] 中找到最小元素
更新和查询都必须及时运行,O(log n)
并且结构必须占用O(n)
空间。
谢谢您的帮助!
我设法用这项Lazy Propagation
技术做到了这一点。
初始化是使用向量而不是数组。
很容易变成最大查询结构...将所有min-s替换为max-s,将数字2100000000替换为-2100000000
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
class IntervalTree
{
int* tree;
int* lazy;
int n;
void build_tree(const vector<int>& v, int node, int a, int b)
{
if (a > b) return;
if (a == b) { tree[node] = v[a]; return; }
build_tree(v, node * 2, a, (a + b) / 2);
build_tree(v, node * 2 + 1, 1 + (a + b) / 2, b);
tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
}
void update_lazy(int node, int a, int b)
{
tree[node] += lazy[node];
if (a != b)
{
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
lazy[node] = 0;
}
void update_tree(int node, int a, int b, int i, int j, int value)
{
if (lazy[node] != 0) update_lazy(node,a,b);
if (a > b || a > j || b < i) return;
if (a >= i && b <= j)
{
tree[node] += value;
if (a != b)
{
lazy[node * 2] += value;
lazy[node * 2 + 1] += value;
}
return;
}
update_tree(node * 2, a, (a + b) / 2, i, j, value);
update_tree(1 + node * 2, 1 + (a + b) / 2, b, i, j, value);
tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
}
int query_tree(int node, int a, int b, int i, int j)
{
if (a > b || a > j || b < i) return 2100000000;
if (lazy[node] != 0) update_lazy(node,a,b);
if (a >= i && b <= j) return tree[node];
int q1 = query_tree(node * 2, a, (a + b) / 2, i, j);
int q2 = query_tree(1 + node * 2, 1 + (a + b) / 2, b, i, j);
return min(q1, q2);
}
public:
IntervalTree(const vector<int>& v)
{
n = v.size();
int s = 2*pow(2, ceil(log2(v.size())));
tree = new int[s];
lazy = new int[s];
memset(lazy, 0, sizeof lazy);
build_tree(v, 1, 0, n - 1);
}
void update(int idx1, int idx2, int add)
{
update_tree(1, 0, n - 1, idx1, idx2, add);
}
int query(int idx1, int idx2)
{
return query_tree(1, 0, n - 1, idx1, idx2);
}
};