- 全局二分：
考虑将问题差分成 “最后一个小于等于 k” 或 “第一个大于等于 k” 的形式，然后考虑先递归左/右儿子。
Code（以找第一个大于等于 k 为例）：
inline int get(int x, int l, int r, int k) {if (l == r) return l;pushdown(x, l, r);if (maxn[lson] >= k) return get(lson, l, mid, k);return get(rson, mid + 1, r, k);
}
- 给定区间内二分：
即在上一类问题的基础上增加了在 \([ql, qr]\) 的区间内的限制，显然可以考虑先正常找到一段被包含的区间，然后调用上面的函数（注意当区间不符合时会给 k 带来的影响）
以查找 \([ql, qr]\) 内第一个 x 使得 \(a_l + a_{l + 1} + .... + a_x \ge k\)。
inline int query(int x, int l, int r, int ql, int qr, int k) {if (ql <= l && qr >= r) {if (sum[x] >= k) return get(x, l, r, k);else return k -= sum[x], 0;}pushdown(x, l, r);if (qr <= mid) return query(lson, l, mid, ql, qr, k);if (ql > mid) return query(rson, mid + 1, r, ql, qr, k);else {int ret = query(lson, l, mid, ql, qr, k);if (!ret) return query(rson, mid + 1, r, ql, qr, k);return ret;}
}
注意到如果这样写就要写两个函数，非常的繁琐，所以考虑压缩掉一个函数。我们发现，当且仅当此区间不符合要求时才会被迫返回，不然一定会递归到叶子结点，所以可以将符合的情况合并到下面：
inline int query(int x, int l, int r, int ql, int qr, int k) {if (ql <= l && qr >= r && sum[x] < k) return k -= sum[x], 0;if (l == r) return l;pushdown(x, l, r);if (qr <= mid) return query(lson, l, mid, ql, qr, k);if (ql > mid) return query(rson, mid + 1, r, ql, qr);else {int ret = query(lson, l, mid, ql, qr, k);if (!ret) return query(rson, mid + 1, r, ql, qr, k);return ret;}
}
例题：【模版】线段树上二分
标程:
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define ll long long
#define int long long
#define pii pair<int, int>
#define mkp make_pair
#define fi first
#define se second
#define tiii tuple<int, int, int>
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
using namespace std;
inline void smax(int &a, int b) { a = max(a, b); }
inline void smin(int &a, int b) { a = min(a, b); }
using namespace __gnu_pbds;const int N = 1e6 + 7;
int n, m, a[N];
int ans[N << 2], tag[N << 2], cov[N << 2];#define mid (l + r >> 1)
#define lson (x << 1)
#define rson (x << 1 | 1)
inline void pushup(int x) { ans[x] = ans[lson] + ans[rson]; }
inline void build(int x, int l, int r) {cov[x] = -1, tag[x] = 0;if (l == r) return ans[x] = a[l], void();build(lson, l, mid);build(rson, mid + 1, r);pushup(x);
}
inline void pushdown(int x, int l, int r) {if (cov[x] != -1) {ans[lson] = (mid - l + 1) * cov[x];cov[lson] = cov[x], tag[lson] = 0;ans[rson] = (r - mid) * cov[x];cov[rson] = cov[x], tag[rson] = 0;cov[x] = -1;} if (tag[x]) {ans[lson] += (mid - l + 1) * tag[x];tag[lson] += tag[x];ans[rson] += (r - mid) * tag[x];tag[rson] += tag[x];tag[x] = 0;}
}
inline void update(int x, int l, int r, int ql, int qr, int val) {if (ql <= l && qr >= r) {ans[x] += (r - l + 1) * val, tag[x] += val;return ;}pushdown(x, l, r);if (ql <= mid) update(lson, l, mid, ql, qr, val);if (qr > mid) update(rson, mid + 1, r, ql, qr, val);pushup(x);
}
inline void cover(int x, int l, int r, int ql, int qr, int val) {if (ql <= l && qr >= r) {ans[x] = (r - l + 1) * val, tag[x] = 0, cov[x] = val;return ;}pushdown(x, l, r);if (ql <= mid) cover(lson, l, mid, ql, qr, val);if (qr > mid) cover(rson, mid + 1, r, ql, qr, val);pushup(x);
}
inline int query(int x, int l, int r, int ql, int qr, int &k) {if (ql <= l && qr >= r && ans[x] < k) return k -= ans[x], -1;if (l == r) return l;pushdown(x, l, r);if (qr <= mid) return query(lson, l, mid, ql, qr, k);if (ql > mid) return query(rson, mid + 1, r, ql, qr, k);else {int ret = query(lson, l, mid, ql, qr, k);if (ret == -1) return query(rson, mid + 1, r, ql, qr, k);return ret;}
}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> m;rep(i, 1, n) cin >> a[i];build(1, 1, n);rep(i, 1, m) {int opt, x, y, k;cin >> opt >> x >> y >> k;if (opt == 1) update(1, 1, n, x, y, k);if (opt == 2) cover(1, 1, n, x, y, k);if (opt == 3) cout << query(1, 1, n, x, y, k) << '\n';}return 0;
}