Why this matters when you build with AI
When a tool is asked for a range query with updates, it reaches for a segment tree or a Fenwick tree first. Those are right when the operation combines cleanly. Many real problems do not combine cleanly. The question might be "how many values in this range are at least k" with a value changed at any time, and no single tree node summary answers it. A tool that cannot find a clean tree often writes a loop over the whole range, which passes the sample and times out at the limit.
Sqrt decomposition is the fallback that does not need a tree. It splits the array into blocks of about sqrt(n) positions, keeps a small summary per block, and answers a query by combining whole-block summaries with a scan of the two partial ends. It is easy to write, which makes it easy to get wrong in small ways: a missing removal from a summary, an off-by-one at a block edge, or a lazy tag that is never pushed into the summary it depends on. The check is still the brute force. Write the slow version, generate random small cases that hit the block edges, and compare every answer.
A prompt to test an AI tool
Give the tool this prompt, then check its answer against the list below.
Write C++17 code for an array of n values and two operations. The first sets a[i] to v. The second counts the positions i in the half-open range [l, r) with a[i] at least k. Use sqrt decomposition with sorted blocks of a size near sqrt(n). Also write a brute force, a random test on 2000 small inputs that tries block sizes 1, 2, 3 and n, and a timing run with n = q = 200000. Report the block sizes you tried and the times from your own run, and say which numbers you measured.A good answer has these parts. The update removes the old value from its block before it inserts the new one. The query handles the left edge, the full blocks and the right edge as three separate loops. The random test uses block sizes that end exactly on the edges. The timing numbers come from a run the tool actually did, with the machine named. Check the update first: a missing removal gives a count that is too high, and the random test finds it on the first input.
Scope and how the code was checked
Every program in this lesson was compiled with g++ -O2 -std=c++17 on the machine that wrote it. That machine runs Linux under WSL2 and uses g++ 15.2.0. The lazy block-tag program was also built with the address and undefined-behaviour sanitizers, which report memory and arithmetic errors at run time, and printed no sanitizer message. Each solver was compared with a brute force on random small inputs before any timing was run.
The timings come from one machine. Two runs of the same benchmark differed by up to 1.4 times for the same program, so read the timings as rough and the ordering between solvers as the thing to check. The answers printed by every solver in the benchmark are the same, which is checked with a checksum. On your machine the times will differ.
No outside source is cited. The claims about cost are proved in the text. The rest is what the programs printed.
The idea: blocks with summaries
Take an array a of n values and a block size B. Block number b holds the positions b * B up to (b + 1) * B - 1. The last block may be shorter when n is not a multiple of B. For each block, keep a summary. The summary depends on the question. For "how many values are at least k", the summary is the list of the block's values in sorted order. Given that list, the count of values at least k in a full block is one binary search.
A query on [l, r) then works in three parts:
- Scan the positions from
lup to the next block edge one at a time. These are the left partial positions. - For each full block that fits inside the range, use its summary. This is one binary search per block.
- Scan the positions from the last block edge up to
r. These are the right partial positions.
An update to one position changes one block. The block's summary is rebuilt for that block only. With a sorted list, that means removing the old value and inserting the new one, which costs time proportional to B.
With B near sqrt(n), a query costs about n / B binary searches plus about 2 * B scans. Both are about sqrt(n). An update costs about B, which is also about sqrt(n).
The problem
This lesson uses one original problem for the worked example. The input is an array of n values. There are two kinds of operation:
U pos value: seta[pos]tovalue.Q l r k: count the positionsiwithl <= i < randa[i] >= k.
The positions and the query range are 0-based and half-open, as in the earlier lessons. The sum is over positions, not distinct values. A segment tree with a sum at each node does not answer this, because the node would need the count of values above a threshold that changes per query.
The standard technique
The code below keeps a sorted list per block. It also has a brute force, a random test, a worked example and a timing run. It was built and run exactly as shown.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// type 1: set a[pos] = value (pos is 0-based).
// type 2: count indices i in [l, r) with a[i] >= k (half-open).
struct Op { int type, x, y, k; };
// Sqrt decomposition: blocks of size B, each block keeps its values sorted.
// Update costs O(B) to move one value inside a sorted list.
// Query costs O((n / B) log B + B): binary search in each full block, scan the ends.
vector<ll> solve_sqrt(const vector<int> &init, const vector<Op> &ops, int B) {
int n = init.size();
vector<int> a = init;
vector<vector<int>> s((n + B - 1) / B);
for (int i = 0; i < n; i++) s[i / B].push_back(a[i]);
for (auto &blk : s) sort(blk.begin(), blk.end());
vector<ll> out;
for (const Op &op : ops) {
if (op.type == 1) {
int i = op.x, v = op.y;
auto &blk = s[i / B];
blk.erase(lower_bound(blk.begin(), blk.end(), a[i]));
blk.insert(upper_bound(blk.begin(), blk.end(), v), v);
a[i] = v;
} else {
int l = op.x, r = op.y, k = op.k;
ll res = 0;
int i = l;
while (i < r && i % B != 0) { res += (a[i] >= k); i++; } // left edge
while (i + B <= r) { // full blocks
const auto &blk = s[i / B];
res += blk.end() - lower_bound(blk.begin(), blk.end(), k);
i += B;
}
while (i < r) { res += (a[i] >= k); i++; } // right edge
out.push_back(res);
}
}
return out;
}
// Log-structure comparison: a Fenwick tree over positions where each node holds
// a Fenwick tree over the values that node can ever contain (collected offline).
// Cost: O(log^2 n) per update and per query.
vector<ll> solve_bit2d(const vector<int> &init, const vector<Op> &ops) {
int n = init.size();
vector<vector<int>> vals(n + 1);
auto cover = [&](int p, int v) { // every outer node that covers position p (0-based)
for (int j = p + 1; j <= n; j += j & -j) vals[j].push_back(v);
};
for (int i = 0; i < n; i++) cover(i, init[i]);
for (const Op &op : ops)
if (op.type == 1) cover(op.x, op.y);
vector<vector<int>> bit(n + 1);
for (int j = 1; j <= n; j++) {
sort(vals[j].begin(), vals[j].end());
vals[j].erase(unique(vals[j].begin(), vals[j].end()), vals[j].end());
bit[j].assign(vals[j].size() + 1, 0);
}
auto inner_add = [&](int j, int v, int delta) {
int idx = lower_bound(vals[j].begin(), vals[j].end(), v) - vals[j].begin();
for (int t = idx + 1; t <= (int)vals[j].size(); t += t & -t) bit[j][t] += delta;
};
auto inner_less = [&](int j, int k) -> ll { // present values in node j that are < k
int idx = lower_bound(vals[j].begin(), vals[j].end(), k) - vals[j].begin();
ll res = 0;
for (int t = idx; t > 0; t -= t & -t) res += bit[j][t];
return res;
};
vector<int> cur = init;
for (int i = 0; i < n; i++)
for (int j = i + 1; j <= n; j += j & -j) inner_add(j, cur[i], +1);
// Every position always holds exactly one value, so a node covering lowbit(j)
// positions has lowbit(j) present values. Values >= k are that count minus the ones < k.
auto prefix_ge = [&](int p, int k) -> ll { // count of i in [0, p) with value >= k
ll res = 0;
for (int j = p; j > 0; j -= j & -j) res += (j & -j) - inner_less(j, k);
return res;
};
vector<ll> out;
for (const Op &op : ops) {
if (op.type == 1) {
int i = op.x, v = op.y;
for (int j = i + 1; j <= n; j += j & -j) {
inner_add(j, cur[i], -1);
inner_add(j, v, +1);
}
cur[i] = v;
} else {
out.push_back(prefix_ge(op.y, op.k) - prefix_ge(op.x, op.k));
}
}
return out;
}
vector<ll> brute(const vector<int> &init, const vector<Op> &ops) {
vector<int> a = init;
vector<ll> out;
for (const Op &op : ops) {
if (op.type == 1) {
a[op.x] = op.y;
} else {
ll res = 0;
for (int i = op.x; i < op.y; i++) res += (a[i] >= op.k);
out.push_back(res);
}
}
return out;
}
void random_tests() {
mt19937 rng(99);
const int ITER = 3000;
for (int it = 0; it < ITER; it++) {
int n = rng() % 40 + 1, V = 10;
vector<int> init(n);
for (auto &x : init) x = rng() % V;
int q = rng() % 60 + 1;
vector<Op> ops;
for (int t = 0; t < q; t++) {
if (rng() % 2) {
ops.push_back({1, (int)(rng() % n), (int)(rng() % V), 0});
} else {
int l = rng() % (n + 1);
int r = l + rng() % (n - l + 1);
ops.push_back({2, l, r, (int)(rng() % (V + 1))});
}
}
auto expect = brute(init, ops);
if (solve_bit2d(init, ops) != expect) {
printf("BIT MISMATCH at iteration %d\n", it);
return;
}
for (int B : {1, 2, 3, 7, n}) {
if (solve_sqrt(init, ops, B) != expect) {
printf("SQRT MISMATCH at iteration %d, B=%d\n", it, B);
return;
}
}
}
printf("random tests: %d inputs, sqrt (5 block sizes) and bit2d match brute force\n", ITER);
}
void worked_example() {
vector<int> init = {5, 1, 4, 2, 8, 3};
vector<Op> ops = {
{2, 0, 6, 4}, // values >= 4 in [0,6)
{1, 1, 9, 0}, // a[1] = 9
{2, 1, 4, 4}, // values >= 4 in [1,4)
{2, 2, 6, 5}, // values >= 5 in [2,6)
};
auto s = solve_sqrt(init, ops, 2);
auto b = solve_bit2d(init, ops);
auto e = brute(init, ops);
for (size_t i = 0; i < s.size(); i++)
printf("query %zu: sqrt=%lld bit2d=%lld brute=%lld\n", i, s[i], b[i], e[i]);
}
void bench() {
const int n = 200000, q = 200000, V = 1000000;
mt19937 rng(5);
vector<int> init(n);
for (auto &x : init) x = rng() % V;
vector<Op> ops;
for (int t = 0; t < q; t++) {
if (rng() % 2) {
ops.push_back({1, (int)(rng() % n), (int)(rng() % V), 0});
} else {
int l = rng() % n;
int r = l + 1 + rng() % (n - l);
ops.push_back({2, l, r, (int)(rng() % V)});
}
}
printf("n=%d ops=%d (half updates, half queries), values < %d\n", n, q, V);
printf("%-14s %8s %10s %12s\n", "solver", "B", "ms", "checksum");
for (int B : {128, 447, 1024}) {
auto t0 = chrono::steady_clock::now();
auto out = solve_sqrt(init, ops, B);
auto t1 = chrono::steady_clock::now();
ll sum = 0;
for (ll x : out) sum = (sum * 31 + x) % 1000000007;
printf("%-14s %8d %10.1f %12lld\n", "sqrt", B, chrono::duration<double, milli>(t1 - t0).count(), sum % 1000000007);
}
auto t0 = chrono::steady_clock::now();
auto out = solve_bit2d(init, ops);
auto t1 = chrono::steady_clock::now();
ll sum = 0;
for (ll x : out) sum = (sum * 31 + x) % 1000000007;
printf("%-14s %8s %10.1f %12lld\n", "bit2d", "-", chrono::duration<double, milli>(t1 - t0).count(), sum % 1000000007);
}
int main(int argc, char **argv) {
if (argc > 1 && string(argv[1]) == "bench") {
bench();
return 0;
}
random_tests();
worked_example();
return 0;
}Compile and run it with these commands:
g++ -O2 -std=c++17 -Wall -Wextra -o sqrt_block sqrt_block.cpp
./sqrt_block
./sqrt_block benchOutput of the first run on the machine that wrote this lesson:
random tests: 3000 inputs, sqrt (5 block sizes) and bit2d match brute force
query 0: sqrt=3 bit2d=3 brute=3
query 1: sqrt=2 bit2d=2 brute=2
query 2: sqrt=1 bit2d=1 brute=1Check the worked example by hand. The array starts as [5, 1, 4, 2, 8, 3]. The first query counts values at least 4 in positions 0 to 5: the values 5, 4 and 8, so 3. The update sets position 1 to 9, which makes the array [5, 9, 4, 2, 8, 3]. The second query counts values at least 4 in positions 1 to 3: 9, 4 and 2 give 2 (the 9 and the 4). The third query counts values at least 5 in positions 2 to 5: 4, 2, 8 and 3 give 1 (the 8).
A count over 200000 positions fits in a 32-bit int. The benchmark checksum is reduced modulo 1000000007 after each step, so it stays small. Without that reduction, a running product of this kind overflows a 64-bit integer, which is undefined behaviour in C++.
Complexity and the constant factor
The sqrt solver costs about (n / B) * log(B) for the binary searches in the full blocks, plus about 2 * B for the partial ends. An update costs about B to move one value inside a sorted list. Choosing B near sqrt(n) balances the two terms. The log factor is small because B is small, so binary search over one block is cheap.
The log structure, here called bit2d, is a Fenwick tree over positions where every node holds its own Fenwick tree over the values that node can ever contain. Its cost is O(log^2 n) per update and per query. For n = 200000, log^2 n is about 310, against about 447 for the sqrt solver's sqrt(n). The difference in growth is small at this size, so the constant factor decides the winner on real hardware.
The bit2d code collects the values offline. It reads the whole operation list first, so it can allocate each node's list once. That preprocessing is included in the timing below, which is the fair comparison for a contest run where the input is read all at once.
Benchmark on the machine that wrote this lesson. The input has 200000 positions, 200000 operations with half updates and half queries, and values below 1000000. The checksum is a fingerprint of all answers, so equal checksums mean the solvers agreed.
n=200000 ops=200000 (half updates, half queries), values < 1000000
solver B ms checksum
sqrt 128 2581.2 31173563
sqrt 447 1171.1 31173563
sqrt 1024 664.6 31173563
bit2d - 1955.8 31173563The second run of the same program printed:
sqrt 128 1910.2 31173563
sqrt 447 898.5 31173563
sqrt 1024 835.6 31173563
bit2d - 2609.8 31173563What the two runs agree on:
- All four solvers print the same checksum, so they gave the same answers.
- The best sqrt setting was B = 1024 in both runs. The bit2d solver was about 3 times slower than that setting in both runs (1956 ms against 665 ms, and 2610 ms against 836 ms).
- Timings moved by up to 1.4 times between runs of the same program, so the gaps between the B = 447 and B = 1024 rows are not reliable. The bit2d row was faster than the B = 128 and B = 447 rows in the first run and slower than them in the second.
The honest reading is this. The log structure has the better growth rate, but its constant factor is large: it keeps one sorted list and one tree per node, and it needs an offline pass to build those lists. At n = 200000, the sqrt solver with a block size near 1024 was faster on this machine. A larger n or a different mix of updates and queries may change that, and the exercise asks you to find where.
Lazy block tags for range updates
Sometimes the update is a range, such as "add x to every value in [l, r)", and the question is the minimum in a range. Walking every position is too slow. Lazy block tags solve this. A tag is a number stored per block that means "add this to every value in the block, but do not write it into the values yet". A full block gets its tag increased. A partial block is updated position by position, and its summary is recomputed.
The summary here is the block minimum without the tag. The real minimum of a block is the summary plus the tag, because the tag shifts every value by the same amount. This is the invariant that makes the code correct: whenever the code reads a value, it adds the tag of that block, and whenever it changes the block's values, it refreshes the summary.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Sqrt decomposition with lazy block tags. Supports range add and range min on [l, r).
// tag[b] is added to every value of block b but not yet written into a[].
// mn[b] is the minimum of a[] over block b, without the tag.
struct SqrtAddMin {
int n, B;
vector<ll> a, tag, mn;
SqrtAddMin(const vector<ll> &v, int blockSize) : n(v.size()), B(blockSize), a(v) {
int nb = (n + B - 1) / B;
tag.assign(nb, 0);
mn.assign(nb, LLONG_MAX);
for (int i = 0; i < n; i++) mn[i / B] = min(mn[i / B], a[i]);
}
void refresh(int b) {
mn[b] = LLONG_MAX;
for (int i = b * B; i < min(n, (b + 1) * B); i++) mn[b] = min(mn[b], a[i]);
}
void add(int l, int r, ll x) {
int i = l;
while (i < r && i % B != 0) { a[i] += x; i++; } // left edge, then fix the block minimum
if (i > l) refresh((l) / B);
while (i + B <= r) { tag[i / B] += x; i += B; } // whole blocks: just the tag
int first = i;
while (i < r) { a[i] += x; i++; } // right edge
if (i > first) refresh((r - 1) / B);
}
ll query(int l, int r) { // min over [l, r), r > l
ll res = LLONG_MAX;
int i = l;
while (i < r && i % B != 0) { res = min(res, a[i] + tag[i / B]); i++; }
while (i + B <= r) { res = min(res, mn[i / B] + tag[i / B]); i += B; }
while (i < r) { res = min(res, a[i] + tag[i / B]); i++; }
return res;
}
};
// Brute force: plain array, plain loops.
struct Naive {
vector<ll> a;
void add(int l, int r, ll x) { for (int i = l; i < r; i++) a[i] += x; }
ll query(int l, int r) {
ll res = LLONG_MAX;
for (int i = l; i < r; i++) res = min(res, a[i]);
return res;
}
};
void random_tests() {
mt19937 rng(777);
const int ITER = 3000;
for (int it = 0; it < ITER; it++) {
int n = rng() % 40 + 1;
vector<ll> v(n);
for (auto &x : v) x = (ll)(rng() % 200) - 100;
int B = rng() % 8 + 1;
SqrtAddMin fast(v, B);
Naive slow{v};
for (int t = 0; t < 60; t++) {
int l = rng() % n;
int r = l + 1 + rng() % (n - l);
if (rng() % 2) {
ll x = (ll)(rng() % 41) - 20;
fast.add(l, r, x);
slow.add(l, r, x);
} else if (fast.query(l, r) != slow.query(l, r)) {
printf("MISMATCH at iteration %d, B=%d\n", it, B);
return;
}
}
}
printf("random tests: %d inputs, 60 ops each, lazy sqrt matches naive array\n", ITER);
}
void worked_example() {
vector<ll> v = {4, 9, 1, 7, 3, 8, 2};
SqrtAddMin t(v, 3);
printf("min[0,7)=%lld\n", t.query(0, 7));
t.add(1, 6, -5); // values 1..5 drop by 5
printf("after add -5 on [1,6): min[0,7)=%lld, min[1,3)=%lld, min[4,7)=%lld\n",
t.query(0, 7), t.query(1, 3), t.query(4, 7));
}
int main() {
worked_example();
random_tests();
return 0;
}Compile and run:
g++ -O2 -std=c++17 -Wall -Wextra -fsanitize=address,undefined -o lazy_sqrt lazy_sqrt.cpp
./lazy_sqrtOutput on the machine that wrote this lesson:
min[0,7)=1
after add -5 on [1,6): min[0,7)=-4, min[1,3)=-4, min[4,7)=-2
random tests: 3000 inputs, 60 ops each, lazy sqrt matches naive arrayCheck the worked example by hand. The array is [4, 9, 1, 7, 3, 8, 2], and its minimum is 1. Adding -5 to positions 1 to 5 gives [4, 4, -4, 2, -2, 3, 2]. The minimum over all positions is -4, the minimum over positions 1 and 2 is -4, and the minimum over positions 4 to 6 is -2.
The tags are the key idea. With block size 3, the blocks are positions 0 to 2, 3 to 5 and 6. The range [1, 6) covers positions 1 and 2 at the end of block 0, and all of block 1. The code adds -5 to positions 1 and 2 directly, adds -5 to the tag of block 1, and does not touch block 2. Reads add the tag back, so every value comes out right.
The sanitizer run printed nothing extra, so the program has no detected out-of-bounds access or undefined arithmetic on this input set. The random tests are a stronger check than one run, because they use 3000 inputs with random block sizes from 1 to 8.
Sqrt rebuilding and heavy and light values
Two more techniques use the same block idea. This lesson does not run code for them. The exercises ask you to write them.
Rebuilding after sqrt(q) operations is for a structure that is expensive to update but cheap to rebuild. Suppose q operations arrive and the structure cannot take an update in less than sqrt(q) time. You keep a short list of recent changes. A query combines the built structure with that list. After sqrt(q) changes, you rebuild the structure from scratch and clear the list. The list never grows past sqrt(q) entries, so each query costs sqrt(q) extra. Rebuilding costs n and happens about sqrt(q) times, which adds n * sqrt(q) in total. For n = q = 200000, that is the same order as the block bound above.
Heavy and light splitting handles values that are frequent. A value is heavy when it appears at least T times in the whole array. There are at most n / T heavy values, because each one takes T positions. For each heavy value you can keep one count per block, which costs (n / T) * (n / B) memory. A light value appears fewer than T times, so a query for it can walk its short list of positions directly. The threshold T is chosen near sqrt(n), so the two sides cost about the same. This design was not run for this lesson.
Hands-on exercise
Work on your own machine with any g++ or clang++ that accepts -std=c++17. Save the first program as sqrt_block.cpp and the second as lazy_sqrt.cpp.
- Build both programs with the commands above. Confirm that the sqrt program prints the random-test line and the three query lines, and that the lazy program prints the three lines shown earlier. If a line says
MISMATCH, read the iteration number and stop there. - Change the block sizes in
benchto 50, 100, 200, 400, 800, 1600, run it, and note which size is fastest on your machine. Run it twice. Write down how far apart the two runs are. - Write a brute force for the lazy program's
querythat uses the sum of the block instead of the minimum, and change the program to answer range sum with range add. The block summary changes from the minimum to a sum. Hint in the answer below.
Show the answer
Step 1: the printed lines must match the outputs shown in this lesson, except that random inputs are fixed by their seeds, so the random-test line is identical on every machine. Step 2: the fastest block size will differ from 1024 on many machines, and the cost curve is flat near the best value. Step 3: a block sum with a tag needs the block length, because a short last block has fewer values. A full-block sum is sum[b] + tag[b] * len, where len is the number of positions in block b. A partial update changes a[i] and adds x to sum[b]. A partial query returns a[i] + tag[b] for each position. Test it with the same random harness, using the sum in place of the minimum in Naive.
Common mistakes
Forgetting to remove the old value
The update must remove the old value from the block's sorted list before inserting the new one. Remove the removal line and the list grows with duplicates, so counts are too high. The real output of the program with that line removed:
SQRT MISMATCH at iteration 0, B=1The three worked-example queries still printed the right values on that version. The random test catches it on its first iteration.
An off-by-one in the full-block loop
The full-block loop uses i + B <= r, which means the block must end at or before r. A common edit is i + B < r. That edit is still correct, because the block that ends exactly at r falls into the right-edge loop and is scanned one value at a time. The random test printed no mismatch for this edit. The cost is only speed when a query ends exactly at a block edge. I did not time this edit, so the size of the slowdown is not measured here.
The lesson is that a wrong bound is not always a wrong answer. Check the answer with the random test, then check the speed with the benchmark.
Forgetting to refresh the block summary after a lazy update
In the lazy program, a partial update changes a[i], so the block minimum mn[b] must be recomputed. Remove that refresh and the minimum goes stale. The real output with the right-edge refresh removed:
MISMATCH at iteration 0, B=6On that version the worked example still printed the right values, so the stale minimum did not change those three answers. The random test with 3000 inputs found it at once.
Using a bigger block than the array needs
With B larger than n, there is one block, and every query is only partial-edge scanning. That is correct but slow for large n. Choose B near sqrt(n), then tune with the benchmark.
Missing the short last block
When n is not a multiple of B, the last block is shorter. A tag or a sum that assumes length B for every block gives a wrong sum. Use the real length of each block, as the rebuilding exercise above does.
Checklist
- Write the brute force first and generate inputs whose windows start and end on block edges.
- Keep one half-open convention for every range in the code.
- For an update that replaces a value, remove the old value before inserting the new one, and keep a copy of the array to know what the old value was.
- Update the block summary after every change to the block, including partial updates made by a lazy structure.
- Use the real length of each block, because the last block can be short.
- Pick the block size near
sqrt(n)first, then tune it with a benchmark on the expected input sizes. - When a log structure is also available, time both on the same input, and include the preprocessing in the timing.
Summary
Sqrt decomposition answers a range question by combining a few whole-block summaries with a scan of the partial ends. It works when no tree node combines cleanly, for example when the question is a count above a threshold under updates. The block size near sqrt(n) balances the query and update costs. Lazy block tags extend the same idea to range updates by storing a shift per block. A log structure can have a better growth rate and still lose on real input sizes because of its constant factor, so the benchmark decides.
Practice
Attempt each problem first, on paper or in code. Each answer is a short argument unless the problem asks for code.
Problem 1: pick the block size
For the sorted-list solver, estimate the best block size for n = 200000 and q = 200000 operations with half updates and half queries. Give the cost formula you used, then check it against the benchmark on your machine.
Hint: a query costs about (n / B) * log B + 2 * B, and an update costs about B. Find the B that minimises the sum of the two costs for half of each.
Show the answer
Taking the query cost alone as (n / B) * log2(B) + 2 * B and the update cost as B, both weighted by half of the operations, the total is about (n / B) * log2(B) / 2 + 1.5 * B per operation. Solving that formula numerically for n = 200000 gives B of about 734, with a cost of about 2400 per operation in the formula's units. The benchmark in this lesson favoured 1024 on this machine, and the times for 447 and 1024 were close. The gap between the formula and the benchmark is the constant factors that the formula ignores. Report both numbers and say which one you trust for your input.
Problem 2: a heavy-value count
Given an array of n values where each value appears at most T times in the whole array, design a structure for "count of positions in [l, r) with value equal to v" that supports point updates. Give the memory and the time per operation.
Hint: each value can be in at most T positions, so a per-value sorted list of positions answers the count with two binary searches. What does an update cost?
Show the answer
Keep, for each value, a sorted list of its positions. A query for value v is two binary searches on that list, costing O(log n). An update to position p from value old to value new removes p from the list for old and inserts it into the list for new. Each list has at most T entries, so each update costs O(T) for the move in the list. Memory is O(n). This is a sketch that I did not run, and the exercise is to test it.
Problem 3: why the constant matters
State a case where the log structure in this lesson would beat the sqrt solver on this machine. Say what you would change in the input and how you would measure it.
Show the answer
The sqrt solver's query cost grows with n / B, and its update cost grows with B. The log structure's cost grows with log^2 n, which grows slowly. For a much larger n, the gap in growth may outweigh the larger constant factor. Measure by timing both solvers on n values of 10^6 and 10^7, with the same operation mix, and check the checksum. The block size for the sqrt solver should be re-tuned at each n. Memory is also part of the comparison, because bit2d stores one list per node.