segment tree

PPTX 30 pages 945.8 KB Free download

30 pages

FaylHub.uz

Download via Telegram

Size 945.8 KB

File type PPTX

Pages 30

Updated Dec 2025

Page preview (5 pages)

Scroll down 👇

1 / 30

segment tree segment tree algorithms and data structures course segment tree a segment tree is a data structure that allows answering range queries over an array effectively, while still being flexible enough to allow modifying the array. this includes finding the sum of consecutive array elements , or finding the minimum element in a such a range in time. between answering such queries the segment tree allows modifying the array by replacing one element, or even change the elements of a whole subsegment (e.g. assigning all elements to any value, or adding a value to all element in the subsegment). algorithms and data structures course segment tree in general a segment tree is a very flexible data structure, and a huge number of problems can be solved with it. additionally it is also possible to apply more complex operations and answer more complex queries. in particular the segment tree can …

2 / 30

ves and and compute the sum of each halve and store them. each of these two halves in turn also split in half, their sums are computed and stored. and this process repeats until all segments reach size 1. algorithms and data structures course segment tree structure in other words we start with the segment , split the current segment in half (if it has not yet become a segment containing a single element), and then calling the same procedure for both halves. for each such segment we store the sum of the numbers on it. we can say, that these segments form a binary tree: the root of this tree is the segment , and each vertex (except leaf vertices) has exactly two child vertices. this is why the data structure is called "segment tree", even though in most implementations the tree is not constructed explicitly. algorithms and data …

3 / 30

tom level, the leaf vertices. a vertex is a leaf vertex, if its corresponding segment covers only one value. therefore we can simply copy the values of the elements a[i]. on the basis of these values, we can compute the sums of the previous level. and on the basis of those, we can compute the sums of the previous, and repeat the procedure until we reach the root vertex. algorithms and data structures course segment tree construction it is convenient to describe this operation recursively: we start the construction at the root vertex and the construction procedure, if called on a not-leaf vertex, first recursively constructs the two child vertices, and than sums up the computed sums of these children. if it is called on a leaf vertex, it simply uses the value of the array. the time complexity of the construction is o(n). algorithms and data structures course segment …

4 / 30

dren. in this case we have no other option as to make two recursive calls, one for each child. first we go to the left child, compute a partial answer for this vertex (i.e. the sum of values of the intersection between the segment of the query and the segment of the left child), then go to the right child, compute the partial answer using that vertex, and then combine the answers by adding them. in other words, since the left child represents the segment and the right child the segment , we compute the sum query using the left child, and the sum query using the right child. algorithms and data structures course segment tree sum queries so processing a sum query is a function that recursively calls itself once with either the left or the right child (without changing the query boundaries), or twice, once for the left …

5 / 30

2 sum = 4 sum = 1 sum = 3 sum = -2 sum = 8 sum = -7 sum = 1 segment tree sum queries: visualization here we want to compute the sum . algorithms and data structures course 1 3 -2 8 -7 1 3 -2 8 -7 1 3 -2 8 -7 1 3 sum = 3 sum = 2 sum = 4 sum = 1 sum = 3 sum = -2 sum = 8 sum = -7 sum = 1 segment tree sum queries: visualization here we want to compute the sum . algorithms and data structures course 1 3 -2 8 -7 1 3 -2 8 -7 1 3 -2 8 -7 1 3 sum = 3 sum = 2 sum = 4 sum = 1 sum = 3 sum = -2 sum = 8 sum = -7 sum = 1 segment tree sum queries: …

Want to read more?

Download all 30 pages for free via Telegram.

Download full file

About "segment tree"

segment tree segment tree algorithms and data structures course segment tree a segment tree is a data structure that allows answering range queries over an array effectively, while still being flexible enough to allow modifying the array. this includes finding the sum of consecutive array elements , or finding the minimum element in a such a range in time. between answering such queries the segment tree allows modifying the array by replacing one element, or even change the elements of a whole subsegment (e.g. assigning all elements to any value, or adding a value to all element in the subsegment). algorithms and data structures course segment tree in general a segment tree is a very flexible data structure, and a …

This file contains 30 pages in PPTX format (945.8 KB). To download "segment tree", click the Telegram button on the left.

Tags: segment tree PPTX 30 pages Free download Telegram