A brief introduction of Segment Tree(II):Update and "Lazy Tag"

Revision en4, by RDFZzzx, 2022-08-02 05:10:23

How to use segment tree?

Build tree and query

You can read this aritical to learn some basic operations of segment tree.

Update and "Lazy Tag"

Lazy Tag

"Lazy Tag" is the most important part in updation. This method can reduce the time complexity to $$$O(\log(n))$$$ for each updation. It's obvious that we can't update the whole tree, or the time complexity will be $$$O(n)$$$ like build tree. To reduce the time complexity, if a segment is not queried now, we don't have to update it at present. We usually give it a tag to record how we update it. For example, if we want to update an array and query the sum of an interval, for each "add" operation, we do not add numbers to each segment, we only have to give a "add tag" to the some segments.

For example, if we want to add $$$2$$$ from $$$2$$$ to $$$5$$$. We give segment number $$$1$$$ and segment number $$$5$$$ an "add tag", to note we should add it up when we query the segment.

void apply_add_tag(int o, int l, int r, ll v)
	sum[o] += (ll)(r - l + 1) * v;
	add[o] += v;

Push Down

When we query the segment which has a tag

Tags data structures, algorithms, segment tree, rmq, lazy updates


  Rev. Lang. By When Δ Comment
en6 English RDFZzzx 2022-08-02 06:29:52 1780 Tiny change: 'nts.\n\n![](https://' -> 'nts.\n\n![ ](https://' (published)
en5 English RDFZzzx 2022-08-02 05:13:24 60
en4 English RDFZzzx 2022-08-02 05:10:23 443
en3 English RDFZzzx 2022-08-02 04:03:38 318
en2 English RDFZzzx 2022-08-02 03:00:48 274
en1 English RDFZzzx 2022-08-02 02:56:20 313 Initial revision (saved to drafts)