Intro:
Let say you have given an array of integers and you have to support two operations:
point update in $$$O(1)$$$ and query in $$$O(\sqrt{N})$$$ of range sum.

---

Example:
$$$N = 10$$$
$$$Array = [7, 10, -2, 6, 12, 8, -10, 6, 5, 11]$$$
Now we have $$$B = \sqrt{N} = 3$$$, so make 3 sized-blocks

Array Blocks $$$= [7,10,-2] [6, 12, 8] [-10, 6, 5] [11, 0, 0]$$$
Append neutral elements to array so that each block is of size $$$B$$$ (For example if the problem is of range sum NEUTRAL = 0 whereas if the problem is range MAX then NEUTRAL = INT_MIN can be taken)

Now,
Array = [7, 10, -2, 6, 12, 8, -10, 6, 5, 11, 0, 0]
Sum = [15, 26, 1, 11]
Here $$$Sum[i]$$$ = sum of elements of $$$i^{th}$$$ block from $$$(i*B)$$$ to $$$(i*B+B-1)$$$

---

Update: let's say I want to update index $$$k = 4$$$ to $$$newValue = 10$$$

Then, update $$$Sum[k/B]=Sum[k/B]-Array[k]+newValue$$$ and then also update $$$Array[k]=newValue$$$
Applying to the example we have
Array = [7, 10, -2, 6, 10, 8, -10, 6, 5, 11, 0, 0]
Sum = [15, 24, 1, 11]

---

Query: let's say I want to get the sum from $$$L$$$ to $$$R$$$ where $$$0\le L\le R\le N$$$
Just like prefix sum view this as $$$query(L,R) = query(0,R)-query(0,L)$$$
So, problem reduces to do $$$query(R) := query(0,R)$$$

Find the block of R as $$$B_R=R/B$$$
Then, $$$Ans =$$$ $$$Sum[0...(B_R-1)]+ \sum_{i=B_R*B}^{R}Array[i]$$$

Observe, that the cost of operation is $$$ B_R+(R-B_R*B) = B_R+(R\%B) \le B + (B-1) = O(B) = O(\sqrt{N}) $$$

---

//C++
int query(int R) {
	ll ans = 0;
	for(int i = 0; i < R / block_size; i++) ans += Sum[i];
	for(int i = (R / block_size) * block_size; i < R; i++) ans += Array[i];
	return ans;
}

int query(int L, int R) {
	return query(R) - query(L - 1);
}

Suppose you are given following problem:

Problem Statement: Find the count of numbers between L to R which have sum of digits = x
where, $$$1 \le L \le R \le 10^{18}$$$ and $$$1\le x\le 100$$$

Naive Solution: Check each of the number satisfying the condition and increment the count

Digit DP Solution:
Lets denote the count from L to R as $$$f(L,R)$$$
Then, the problem can be again rewritten as $$$f(L,R) = f(0,R) - f(0,L-1)$$$

Now the problem is to find $$$f(0,R)$$$ for any R
From the constraints of the problem statement you might have guessed that one of the dp states would be the sum of digits i.e. $$$x$$$ but what is the second state?
Its the number of digits!!
For now lets forget about the constraint that the numbers should be $$$\le R$$$
Just think we have upto $$$N$$$ digits and sum of digits should be $$$x$$$. And count that!

$$$dp[N][x]$$$ denotes the count of numbers which have sum of digits $$$=x$$$ and number of digits $$$\le N$$$
Then, $$$dp[N][x] = \sum_{k=0}^{9} dp[N-1][x-k]$$$

All good??
Alright! Moving ahead!

Now, this dp counts the number without the constraint $$$\le R$$$.
Suppose $$$R = 4258$$$ and $$$x=11$$$
Then, we should not count $$$4430$$$ because $$$4430\ge 4258$$$, but how our dp will know we are exceeding R?

We can include one more state or two $$$dp$$$ arrays $$$dp_1$$$ and $$$dp_2$$$
$$$dp_1[N][x] = $$$ count of the numbers under tight constraint
$$$dp_2[N][x] = $$$ count of the numbers with no constraint as such (so $$$dp_2$$$ will behave as it is we discussed above)

Now you may be asking what is tight constraint?
Ans: at the $$$N^{th}$$$ digit we will check if this digit is less or equal to the $$$N^{th}$$$ of $$$R$$$
Denote $$$R_N$$$ as Nth digit of R,
Then, $$$dp_1[N][x] = dp_1[N-1][x-R_N] + \sum_{k=0}^{R_N-1} dp_2[N-1][x-k]$$$

And, for $$$dp_2$$$ its already unconstrained so its chill there :)
$$$dp_2[N][x] = \sum_{k=0}^{9} dp_2[N-1][x-k]$$$

---