I recently solved 1439C - Greedy Shopping using a segment tree which stores the sum(sum array), min(mn array) and max(mx array) 306106940, I used the following function to process the queries:

pii GET(int id, int l, int r, int x) {
	if(x < mn[id]) return mp(0, 0);
	if(x >= sum[id]) return mp(r-l, sum[id]);
	PUSH(id, l, r);
	pii p1 = GET(lc, l, mid, x); pii p2 = GET(rc, mid, r, x-p1.Y);
	return mp(p1.X+p2.X, p1.Y+p2.Y);
}

At first glance, I thought the time complexity should be O(log(n)²), since the purchased items form some blocks of the array. Since each block at least halves the remaining money, we have O(log(n)) blocks in the array. More so, each block of size k corresponds to O(log(k)) nodes in the segment tree, meaning we must traverse O(log(n)²) blocks in the segment tree, however increasing the number of blocks decreases the sum of the logarithms of the block sizes, so we might traverse less nodes in the segment tree. Despite trying, I could not figure out a definite time complexity for this function and I would greatly appreciate any help to form a vague proof of this function's actual time complexity.