Searching for an array prefix with a given amount. (using segment trees)

→ Обратите внимание

До соревнования
Spectral::Cup 2026 Round 1 (Codeforces Round 1094, Div. 1 + Div. 2)
40:58:00
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	Qingyu	157
2	adamant	153
3	Um_nik	146
3	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя weakestOsuPlayer_244

Searching for an array prefix with a given amount. (using segment trees)

Автор weakestOsuPlayer_244, история, 6 лет назад, По-английски

While learning about segment tree I came across this problem:-

The task is as follows: for a given value x we have to quickly find smallest index i such that the sum of the first i elements of the array a[] is greater or equal to x (assuming that the array a[] only contains non-negative values).

Link-https://cp-algorithms.com/data_structures/segment_tree.html

The solution mentions storing prefix sums in the segment trees.

I cannot figure out how to build up a segment tree of prefix sums. Also how is it different from the range sums?

segement tree, prefix sum

weakestOsuPlayer_244
6 лет назад
8

Комментарии (7)

Показать архивные | Написать комментарий?

mamme_hunter

6 лет назад, скрыть # |

← Rev. 2 →

No, we don't need to store the prefix sum. We just need to build the simple sum segment tree, it only differs in the way we query the segment tree. Let the required sum be K, idx represent the index of the segment tree and l and r be the array range it covers, then code will look like,

int query(int idx, int l, int r, int K){
    if( l == r )
        return l;
    int md = (l+r)/2;
    if( seg[2*idx] >= K ) // left child contains the required index
        return query(2*idx, l, md, K);
    else
        return query(2*idx+1, md+1, r, K-seg[2*idx]); // right segment don't have sum of left segment
}

/*********************************
if( seg[1] < K ){
    // answer doesn't exist
}else{
    ans = query(1, 0, n-1, K);
}
********************************/

→ Ответить

weakestOsuPlayer_244

6 лет назад, скрыть # ^ |

return query(2*idx+1, md+1, r, K-seg[2*idx]);

This is how I understood your code. Supposing the left child doesn't have the sum>=K so we go to right child and look for the K-left child sum. Now if the right child's sum is greater than K-left child sum the l of the right child will be the answer. (since the sum of left child +this right child will end up greater than K)

This is how it is?

→ Ответить

mamme_hunter

6 лет назад, скрыть # ^ |

← Rev. 2 →

Yes, since we know answer do exist (see comments in the code), then if answer is not in the left child then answer will be in the segment covered by right child and hence we call the same function on the right child with sum of the left child removed

→ Ответить

weakestOsuPlayer_244

6 лет назад, скрыть # ^ |

Thanks a lot!

→ Ответить

Gheal

6 лет назад, скрыть # |

Do you need to update the elements of the array?

If no, use binary search to find the first position.

My code (C++)

#include<bits/stdc++.h>
#define NMAX 200009

using namespace std;
typedef long long ll;

ll sum[NMAX], n, x;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> x;

    for(ll i = 0; i < n; i++){

        cin >> sum[i];

        if(i > 0)
            sum[i] += sum[i - 1];
    }

    cout << lower_bound(sum, sum + n , x) - sum; /// Note: elements are numerated from 0

    return 0;
}

Sample tests

Otherwise, my solution would be to use a segment tree with range sums.

My code(C++)

#include<bits/stdc++.h>
#define NMAX 200009

using namespace std;
typedef long long ll;

struct node{
    ll l, r, sum;
}segmTree[NMAX * 20]; /// 20 > log2(200009)

ll leaves[NMAX], n, v[NMAX]; /// intervals with one element

ll parent(ll curNode){
    return (curNode-1)/2; /// (2*k+2-1)/2 = (2*k+1-1)/2 = k
}
ll sibling(ll curNode){
    if(curNode % 2 == 0) return curNode - 1; /// is of the form 2*k + 2; its sibling is 2*k+1
    else return curNode + 1;
}
void construct(ll low, ll up, ll currentNode){ /// recursive function that initializes the segment tree

    segmTree[currentNode] = {low, up, 0};

    if(low < up){

        construct(low, (low + up) / 2, currentNode * 2 + 1); /// child 1 of node k is 2*k+1
        construct( (low + up) / 2 + 1, up, currentNode * 2 + 2); /// child 2 of node k is 2*k+2
    }
    else leaves[low] = currentNode; /// one element
}
void update(ll currentNode, ll val){
    segmTree[currentNode].sum = val;

    if(currentNode == 0) /// root; has no children
        return;

    update(parent(currentNode), val + segmTree[sibling(currentNode)].sum);
}
ll index(ll targetSum, ll seqLeft){
    ll currentNode=leaves[seqLeft];

    if(segmTree[currentNode].sum>=targetSum) /// solution
        return seqLeft;

    while(currentNode !=0  && segmTree[parent(currentNode)].sum < targetSum)
        currentNode = parent(currentNode);

    return index(targetSum - segmTree[currentNode].sum, segmTree[currentNode].r + 1);
    /// we have added the sum from 'l' to 'r', so we will subtract it from the target sum
    /// we will search from 'r' + 1 to find the first index
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll queries, queryType, queryParam1, queryParam2;

    cin>>n>>queries;

    for(ll i = 1; i <= n; i++)
        cin>>v[i];

    construct(1, n, 0); /// 0 is the root

    for(ll i = 1; i <= n; i++){
        update(leaves[i], v[i]); /// the 'update' function will update range sums
    }

    for(ll i=0; i < queries; i++){
        cin>>queryType;
        if(queryType == 1){

            cin >> queryParam1 >> queryParam2; /// v[queryParam1] becomes v[queryParam2]
            update(leaves[queryParam1], queryParam2);
        }
        else{
            cin >> queryParam1;
            cout << index(queryParam1, 1) << '\n'; /// the first index of the sum greater or equal to queryParam1
            /// the sequence starts from 1
        }
    }
    return 0;
}

Sample tests

Input 1:
5 5
1 2 3 4 5
2 6
2 7
1 4 1
2 6
2 8

Output 1:
3
4
3
5

Input 2:
4 1
1 2 3 4
2 11

Output 2:
5

→ Ответить

weakestOsuPlayer_244

6 лет назад, скрыть # ^ |

Thanks for the detailed implementation. Yes, I was looking for a O(log n) implementation using segment tree.

→ Ответить

om_ashish_soni

4 года назад, скрыть # |

template<typename T>int find_prefix_seg(vt & t,int v,int tl,int tr,int x){
	if(x>t[v]) return -1;
	if(tl==tr){
		return tl;
	}
	int tm=MID(tl,tr);
	if(t[2*v+1]>=x) return find_prefix_seg(t,v*2+1,tl,tm,x);
	return find_prefix_seg(t,v*2+2,tm+1,tr,x-t[v*2+1]);
}

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 24.04.2026 00:37:01 (g2).

Десктопная версия, переключиться на мобильную.

При поддержке