线段树
建树O(n),查询/修改O(logn)
ll a[N];
struct Node
{
int l, r; //区间范围
ll sum; //询问值
ll lazy; //懒标记
} tr[N * 4]; //若存在无法通过递归得到的信息应当一并写入Node
void pushup(int u) //由子节点信息推算父节点信息
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u) //下推懒标记
{
auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if (root.lazy)
{
left.lazy += root.lazy, left.sum += (ll)(left.r - left.l + 1) * root.lazy;
right.lazy += root.lazy, right.sum += (ll)(right.r - right.l + 1) * root.lazy;
root.lazy = 0;
}
}
void build(int u, int l, int r)
{
if (l == r)
{
tr[u] = {l, r, a[l], 0};
}
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, int d) //修改区间[l,r]信息
{
if (l <= tr[u].l && tr[u].r <= r) //节点区间已被完全包含在[l, r]中
{
tr[u].sum += (ll)(tr[u].r - tr[u].l + 1) * d;
tr[u].lazy += d;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) //分治处理左右子树
{
modify(u << 1, l, r, d);
}
if (r > mid)
{
modify(u << 1 | 1, l, r, d);
}
pushup(u);
}
}
ll query(int u, int l, int r) //在区间[l,r]中进行查询
{
if (l <= tr[u].l && tr[u].r <= r) //节点区间已被完全包含在[l, r]中
{
return tr[u].sum;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
ll sum = 0;
if (l <= mid)
{
sum += query(u << 1, l, r);
}
if (r > mid)
{
sum += query(u << 1 | 1, l, r);
}
return sum;
}
主席树(可持久化线段树)
查询/修改O(logn)
例题
给定长度为 N 的整数序列 A,下标为 1∼N。
现在要执行 M 次操作,每次操作为给出三个整数 l,r,k,求 A[l],A[l+1],…,A[r] (即A的下标区间 [l,r])中第k小的数是多少。
int a[N];
int root[N], idx; //[1, i]区间的主席树的根节点
vector<int> nums;
struct Node
{
int l, r;
int cnt;
} tr[N << 5];
int find(int x)
{
return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}
int build(int l, int r) //建树
{
int p = ++idx;
if (l == r)
{
return p;
}
int mid = l + r >> 1;
tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
return p;
}
int insert(int p, int l, int r, int x)
{
int q = ++idx;
tr[q] = tr[p]; //复制
if (l == r)
{
tr[q].cnt++;
return q;
}
int mid = l + r >> 1;
if (x <= mid) //加新点
{
tr[q].l = insert(tr[p].l, l, mid, x);
}
else
{
tr[q].r = insert(tr[p].r, mid + 1, r, x);
}
tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
return q;
}
int query(int q, int p, int l, int r, int k)
{
if (l == r)
{
return l;
}
int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt; //求出[l,r]的值
int mid = l + r >> 1;
if (k <= cnt) //按需递归
{
return query(tr[q].l, tr[p].l, l, mid, k);
}
else
{
return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}
}
int main()
{
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
nums.push_back(a[i]);
}
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end()); //去重
root[0] = build(0, nums.size() - 1);
for (int i = 1; i <= n; i++) //初始化
{
root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));
}
while (m--)
{
int l, r, k;
cin >> l >> r >> k;
cout << nums[query(root[r], root[l - 1], 0, nums.size() - 1, k)] << endl;
}
return 0;
}
说错了吧,建立线段树是O(nlog2n)
呃,一共就4n个节点,为什么是O(nlog2n)呢?
二分诶
哦,忘了