The ZKW segment tree is a non-recursive data structure that performs bottom-up updates and queries. It is often used as a replacement for Fenwick trees when range updates and range queries are needed. The key concept is to use two "shrinking" pointers (l and r) that move upward from the leaf level. To range updates with lazy tags, we use permanent lazy propagation to avoid the overhead of pushdown operations.
Basic Range Update and Query
The following implementation supports range addition and range sum queries. The tree is built over a power-of-two size. Two pointers l and r are initialized to the left and right boundaries expanded by one leaf on each side. During the loop, when l is odd we process its right sibling, and when r is even we process its left sibling. Lazy tags are stored for each node, and after the loop we update the ancestors of l and r.
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 5;
int n, q, offset;
ll arr[MAXN];
ll seg[MAXN << 2], lazy[MAXN << 2];
void build() {
offset = 1;
while (offset < n + 2) offset <<= 1;
for (int i = 1; i <= n; ++i)
seg[offset + i] = arr[i];
for (int i = offset + n; i >= 2; --i)
seg[i >> 1] += seg[i];
}
void add(int l, int r, ll val) {
l += offset - 1;
r += offset + 1;
ll width = 1;
while ((l ^ r) != 1) {
if (!(l & 1)) { seg[l ^ 1] += width * val; lazy[l ^ 1] += val; }
if (r & 1) { seg[r ^ 1] += width * val; lazy[r ^ 1] += val; }
l >>= 1; r >>= 1;
width <<= 1;
seg[l] = seg[l << 1] + seg[l << 1 | 1] + lazy[l] * width;
seg[r] = seg[r << 1] + seg[r << 1 | 1] + lazy[r] * width;
}
while (l >= 1) {
l >>= 1;
width <<= 1;
seg[l] = seg[l << 1] + seg[l << 1 | 1] + lazy[l] * width;
}
}
ll query(int l, int r) {
l += offset - 1;
r += offset + 1;
ll res = 0, left_cnt = 0, right_cnt = 0, width = 1;
while ((l ^ r) != 1) {
if (!(l & 1)) { res += seg[l ^ 1]; left_cnt += width; }
if (r & 1) { res += seg[r ^ 1]; right_cnt += width; }
l >>= 1; r >>= 1;
width <<= 1;
res += lazy[l] * left_cnt + lazy[r] * right_cnt;
}
for (; l >= 1; l >>= 1)
res += lazy[l] * (left_cnt + right_cnt);
return res;
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; ++i) scanf("%lld", &arr[i]);
build();
while (q--) {
int op, l, r; ll x;
scanf("%d", &op);
if (op == 1) {
scanf("%d%d%lld", &l, &r, &x);
add(l, r, x);
} else {
scanf("%d%d", &l, &r);
printf("%lld\n", query(l, r));
}
}
return 0;
}
Matrix Operations on a Segment Tree (Sasha and Array)
Since matrix multiplication is associative, we can replace the numeric values with 2×2 matrices and implement range multiplication and sum queries. The lazy tag is now a matrix factor that is multiplied with the stored sums. This allows us to compute Fibonacci numbers efficiently on intervals.
#include <cstdio>
#include <cstring>
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;
int n, m, arr[MAXN], offset;
struct Mat {
int a[2][2];
Mat() { memset(a, 0, sizeof a); }
void identity() { a[0][0] = a[1][1] = 1; }
bool is_identity() const {
return a[0][0] == 1 && a[0][1] == 0 && a[1][0] == 0 && a[1][1] == 1;
}
Mat operator*(const Mat &other) const {
Mat res;
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
for (int k = 0; k < 2; ++k)
res.a[i][j] = (res.a[i][j] + (long long)a[i][k] * other.a[k][j]) % MOD;
return res;
}
Mat operator+(const Mat &other) const {
Mat res;
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
res.a[i][j] = (a[i][j] + other.a[i][j]) % MOD;
return res;
}
};
Mat base, start;
struct Node {
Mat sum, tag;
} tree[MAXN << 2];
Mat fastPow(Mat mat, int power) {
Mat res; res.identity();
while (power) {
if (power & 1) res = res * mat;
mat = mat * mat;
power >>= 1;
}
return res;
}
void build() {
offset = 1;
while (offset < n + 2) offset <<= 1;
for (int i = 1; i <= n; ++i) {
tree[offset + i].sum = start * fastPow(base, arr[i] - 1);
}
for (int i = offset + n; i >= 1; --i) {
tree[i >> 1].sum = tree[i >> 1].sum + tree[i].sum;
if (i <= offset) tree[i].tag.identity();
}
}
void modify(int l, int r, const Mat &val) {
l += offset - 1;
r += offset + 1;
while ((l ^ r) != 1) {
if (!(l & 1)) { tree[l ^ 1].sum = tree[l ^ 1].sum * val; tree[l ^ 1].tag = tree[l ^ 1].tag * val; }
if (r & 1) { tree[r ^ 1].sum = tree[r ^ 1].sum * val; tree[r ^ 1].tag = tree[r ^ 1].tag * val; }
l >>= 1; r >>= 1;
tree[l].sum = (tree[l << 1].sum + tree[l << 1 | 1].sum) * tree[l].tag;
tree[r].sum = (tree[r << 1].sum + tree[r << 1 | 1].sum) * tree[r].tag;
}
while (l > 1) {
l >>= 1;
tree[l].sum = (tree[l << 1].sum + tree[l << 1 | 1].sum) * tree[l].tag;
}
}
Mat query(int l, int r) {
l += offset - 1;
r += offset + 1;
Mat left_res, right_res;
while ((l ^ r) != 1) {
if (!(l & 1)) left_res = left_res + tree[l ^ 1].sum;
if (r & 1) right_res = right_res + tree[r ^ 1].sum;
l >>= 1; r >>= 1;
left_res = left_res * tree[l].tag;
right_res = right_res * tree[r].tag;
}
Mat ans = left_res + right_res;
for (; l > 1; l >>= 1) ans = ans * tree[l].tag;
return ans;
}
int main() {
base.a[0][1] = base.a[1][0] = base.a[1][1] = 1;
start.a[0][0] = start.a[0][1] = 1;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]);
build();
while (m--) {
int op, l, r, x;
scanf("%d%d%d", &op, &l, &r);
if (op == 1) {
scanf("%d", &x);
Mat p = fastPow(base, x);
modify(l, r, p);
} else {
printf("%d\n", query(l, r).a[0][0]);
}
}
return 0;
}
Power Sockets – Greedy Insertion with Segment Tree
We want to place chains of sockets so that the total number of sockets reaches a target k as quickly as possible. The greedy strategy is to insert the longest available chain first, breaking it in half each time you place a node. We maintain a segment tree over depth indices, storing the number of sockets at each depth. We need to find the first available depth (lowest depth with a socket) and then add sockets at certain depths depending on chain length. Also, we may need binary search to find the depth where the cumulative sum reaches k.
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 5;
const int INF = 0x3f3f3f3f;
int n, a[MAXN], ans = INF;
ll k;
struct SegTree {
struct Node { int l, r; ll sum, lazy; } t[MAXN << 2];
void push_up(int p) { t[p].sum = t[p<<1].sum + t[p<<1|1].sum; }
void push_down(int p) {
if (!t[p].lazy) return;
int mid = (t[p].l + t[p].r) >> 1;
t[p<<1].sum += t[p].lazy * (mid - t[p].l + 1);
t[p<<1].lazy += t[p].lazy;
t[p<<1|1].sum += t[p].lazy * (t[p].r - mid);
t[p<<1|1].lazy += t[p].lazy;
t[p].lazy = 0;
}
void build(int p, int l, int r) {
t[p].l = l; t[p].r = r; t[p].sum = t[p].lazy = 0;
if (l == r) return;
int mid = (l + r) >> 1;
build(p<<1, l, mid);
build(p<<1|1, mid+1, r);
}
void update(int p, int l, int r, ll val) {
if (t[p].l >= l && t[p].r <= r) {
t[p].sum += (t[p].r - t[p].l + 1) * val;
t[p].lazy += val;
return;
}
push_down(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid) update(p<<1, l, r, val);
if (r > mid) update(p<<1|1, l, r, val);
push_up(p);
}
ll query(int p, int l, int r) {
if (t[p].l >= l && t[p].r <= r) return t[p].sum;
push_down(p);
ll res = 0;
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid) res += query(p<<1, l, r);
if (r > mid) res += query(p<<1|1, l, r);
return res;
}
// find the leftmost position with a socket
int first_pos(int p) {
push_down(p);
if (t[p].l == t[p].r) return t[p].l;
if (t[p<<1].sum) return first_pos(p<<1);
else return first_pos(p<<1|1);
}
// find the smallest depth where cumulative sum reaches k
int binary_search(int p, ll target) {
push_down(p);
if (t[p].l == t[p].r) return t[p].l;
if (t[p<<1].sum >= target) return binary_search(p<<1, target);
else return binary_search(p<<1|1, target - t[p<<1].sum);
}
} tree;
int main() {
scanf("%d%lld", &n, &k);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
sort(a+1, a+n+1, greater<int>());
tree.build(1, 1, MAXN);
for (int i = 1; i <= n; ++i) {
int depth;
if (i == 1) depth = 0;
else {
depth = tree.first_pos(1);
tree.update(1, depth, depth, -1);
}
if (a[i] & 1) // odd length
tree.update(1, depth+2, depth + a[i]/2 + 1, 2);
else {
tree.update(1, depth+2, depth + a[i]/2, 2);
tree.update(1, depth + a[i]/2 + 1, depth + a[i]/2 + 1, 1);
}
if (tree.query(1, 1, MAXN) >= k) {
ans = min(ans, tree.binary_search(1, k));
}
}
printf("%d\n", ans == INF ? -1 : ans);
return 0;
}
Greedy Shopping – Non-Decreasing Array with Range Assignment
After every assignment operation, the sequence remains non-decreasing. We can then perform binary search on the segment tree to find the first position where the minimum value is ≤ remaining money. The segment tree stores the minimum value per node and the sum, along with a lazy tag that represents a set operation (not addition).
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 3e5 + 5;
int n, m;
ll init_arr[MAXN];
struct SegTree {
struct Node { int l, r; ll sum, min_val, tag; } t[MAXN << 2];
void push_up(int p) {
t[p].sum = t[p<<1].sum + t[p<<1|1].sum;
t[p].min_val = min(t[p<<1].min_val, t[p<<1|1].min_val);
}
void push_down(int p) {
if (!t[p].tag) return;
int mid = (t[p].l + t[p].r) >> 1;
t[p<<1].sum = t[p].tag * (mid - t[p].l + 1);
t[p<<1].min_val = t[p].tag;
t[p<<1].tag = t[p].tag;
t[p<<1|1].sum = t[p].tag * (t[p].r - mid);
t[p<<1|1].min_val = t[p].tag;
t[p<<1|1].tag = t[p].tag;
t[p].tag = 0;
}
void build(int p, int l, int r) {
t[p].l = l; t[p].r = r;
if (l == r) {
t[p].sum = t[p].min_val = init_arr[l];
return;
}
int mid = (l + r) >> 1;
build(p<<1, l, mid);
build(p<<1|1, mid+1, r);
push_up(p);
}
void assign(int p, int l, int r, ll val) {
if (t[p].l >= l && t[p].r <= r) {
t[p].sum = val * (t[p].r - t[p].l + 1);
t[p].min_val = val;
t[p].tag = val;
return;
}
push_down(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid) assign(p<<1, l, r, val);
if (r > mid) assign(p<<1|1, l, r, val);
push_up(p);
}
// find first index with min_val <= limit
int find_first(int p, ll limit) {
push_down(p);
if (t[p].l == t[p].r) return t[p].l;
if (t[p<<1].min_val <= limit) return find_first(p<<1, limit);
if (t[p<<1|1].min_val <= limit) return find_first(p<<1|1, limit);
return n + 1;
}
// query from position x to right, spending money, return number of elements taken
int query_spend(int p, int x, ll &money) {
push_down(p);
if (t[p].min_val > money) return 0;
int mid = (t[p].l + t[p].r) >> 1;
if (t[p].l >= x) {
if (money >= t[p].sum) {
money -= t[p].sum;
return t[p].r - t[p].l + 1;
}
}
int res = 0;
if (x <= mid) res += query_spend(p<<1, x, money);
res += query_spend(p<<1|1, x, money);
return res;
}
} tree;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%lld", &init_arr[i]);
tree.build(1, 1, n);
while (m--) {
int op, x; ll y;
scanf("%d%d%lld", &op, &x, &y);
if (op == 1) {
int pos = tree.find_first(1, y);
if (pos > x) continue;
tree.assign(1, pos, x, y);
} else {
printf("%d\n", tree.query_spend(1, x, y));
}
}
return 0;
}