Here you can find realization of segment tree, an useful data structure used to store information and calculate a lot of functions on ranges effectively. The only limitation - this function must be associative.
- segment tree for getting sum on range [i, j] of initial array + updating one element
- segment tree for getting max number on range [i, j] of initial array
- persistent segment tree
- segment tree with lazy propagation (updating whole ranges)
Building tree - O(n)
Range Sum Query / Range Max Query - O(logn)
Updating one element - O(logn)
- Tyapkina Regina - @renett-t
- Savincheva Angelina - @InfInf-prog
- Genatulin Ilnas - @Genatula
May, 2021
11-001 ITIS KFU