New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

About the segment tree - Interval Update Operation #591

Closed
Desgard opened this Issue Aug 22, 2017 · 8 comments

Comments

Projects
None yet
3 participants
@Desgard
Copy link
Contributor

Desgard commented Aug 22, 2017

Category

  • Bug
  • Feature Request
  • Question

Brief Intro

At the beginning, I wanted to add the Interval Update Operation in segment tree. But I found it applied to generics. So I can't program for some special situation.

But the interval update operation is important for segment I think.

So can I make a new segment tree to deal with mathematical problems? Just to support Int, Double and so on.

@kelvinlauKL

This comment has been minimized.

Copy link
Member

kelvinlauKL commented Aug 22, 2017

Could you explain some of the changes you're going to make? We've had requests to rewrite topics before, but our stance is to not allow for updates unless it is clear that the new version is much better.

It takes a lot of time and effort to write one. To respect the authors, we want to set the bar for a rewrite high. I'm not familiar with the significance of the "update operation". In general, a rewrite should do the following:

  • make the article easier to understand (simplify concepts and wording)
  • add critical content related to the topic

If you're confident you can do a rewrite that will be a clear improvement to the current article, please first create a topic outline for us to review and notes about the changes you're going to make.

@Desgard

This comment has been minimized.

Copy link
Contributor

Desgard commented Aug 23, 2017

@kelvinlauKL I have completed a demo for this update operation. It is order to a range.

In this case, it is [0, 3] this range.

public class LazySegmentTree {
    
    private var value: Int
    
    private var leftBound: Int
    
    private var rightBound: Int
    
    private var leftChild: LazySegmentTree?
    
    private var rightChild: LazySegmentTree?
    
    // Interval Update Lazy Element
    private var lazyValue: Int
    
    // MARK: - Push Up Operation
    private func pushUp(lson: LazySegmentTree, rson: LazySegmentTree) {
        self.value = lson.value + rson.value
    }
    
    // MARK: - Push Down Operation
    private func pushDown(round: Int, lson: LazySegmentTree, rson: LazySegmentTree) {
        if lazyValue != 0 {
            lson.lazyValue += lazyValue
            rson.lazyValue += lazyValue
            lson.value += lazyValue * (round - (round >> 1))
            rson.value += lazyValue * (round >> 1)
            lazyValue = 0
        }
    }
    
    public init(array: [Int], leftBound: Int, rightBound: Int) {
        self.leftBound = leftBound
        self.rightBound = rightBound
        self.value = 0
        self.lazyValue = 0
        
        if leftBound == rightBound {
            value = array[leftBound]
            return
        }
        
        let middle = (leftBound + rightBound) / 2
        leftChild = LazySegmentTree(array: array, leftBound: leftBound, rightBound: middle)
        rightChild = LazySegmentTree(array: array, leftBound: middle + 1, rightBound: rightBound)
        pushUp(lson: leftChild!, rson: rightChild!)
        
    }
    
    public convenience init(array: [Int]) {
        self.init(array: array, leftBound: 0, rightBound: array.count - 1)
    }
    
    public func query(leftBound: Int, rightBound: Int) -> Int {
        if leftBound <= self.leftBound && self.rightBound <= rightBound {
            return value
        }
        guard let leftChild  = leftChild  else { fatalError("leftChild should not be nil") }
        guard let rightChild = rightChild else { fatalError("leftChild should not be nil") }
        
        pushDown(round: self.rightBound - self.leftBound + 1, lson: leftChild, rson: rightChild)
        
        let middle = (self.leftBound + self.rightBound) / 2
        var result: Int = 0
        
        if leftBound <= middle { result +=  leftChild.query(leftBound: leftBound, rightBound: rightBound) }
        if rightBound > middle { result += rightChild.query(leftBound: leftBound, rightBound: rightBound) }
        
        return result
    }
    
    // MARK: - One Item Update
    public func update(index: Int, incremental: Int) {
        if self.leftBound == self.rightBound {
            self.value += incremental
            return
        }
        guard let leftChild  = leftChild  else { fatalError() }
        guard let rightChild = rightChild else { fatalError() }
        
        let middle = (self.leftBound + self.rightBound) / 2
        
        if index <= middle { leftChild.update(index: index, incremental: incremental) }
        else { rightChild.update(index: index, incremental: incremental) }
        pushUp(lson: leftChild, rson: rightChild)
    }
    
    // MARK: - Interval Item Update
    public func update(leftBound: Int, rightBound: Int, incremental: Int) {
        if leftBound <= self.leftBound && self.rightBound <= rightBound {
            self.lazyValue += incremental
            self.value += incremental * (self.rightBound - self.leftBound + 1)
            return 
        }
        
        guard let leftChild = leftChild else { fatalError() }
        guard let rightChild = rightChild else { fatalError() }
        
        pushDown(round: self.rightBound - self.leftBound + 1, lson: leftChild, rson: rightChild)
        
        let middle = (self.leftBound + self.rightBound) / 2
        
        if leftBound <= middle { leftChild.update(leftBound: leftBound, rightBound: rightBound, incremental: incremental) }
        if middle < rightBound { rightChild.update(leftBound: leftBound, rightBound: rightBound, incremental: incremental) }
        
        pushUp(lson: leftChild, rson: rightChild)
    }
    
}

let array = [1, 2, 3, 4]

let sumSegmentTree = LazySegmentTree(array: array)

print(sumSegmentTree.query(leftBound: 0, rightBound: 3)) // 10 = 1 + 2 + 3 + 4
sumSegmentTree.update(index: 1, incremental: 2)
print(sumSegmentTree.query(leftBound: 0, rightBound: 3)) // 12 = 1 + 4 + 3 + 4
sumSegmentTree.update(leftBound: 0, rightBound: 2, incremental: 2)
print(sumSegmentTree.query(leftBound: 0, rightBound: 3)) // 18 = 3 + 6 + 5 + 4
@Desgard

This comment has been minimized.

Copy link
Contributor

Desgard commented Aug 23, 2017

I only coded for SumSegmentTree, but it can be extended by fixing the pushDown function and the meaning of lazyValue.

And in my opinion, the most important operations of the Segment Tree are pushUp and pushDown. This can make our Segment Tree sustainable, which means query many times and update many times. 😊

ps: I'll try to write a article to introduce it. It may spend a lot of time for me because of my bad English. 🤣 🤣

@kelvinlauKL

This comment has been minimized.

Copy link
Member

kelvinlauKL commented Aug 23, 2017

I just gave the original Segment Tree a read. It does a good job explaining what it's good for and how to solve it.

How do you feel about appending this information to the current article? You could start off something like this:

This implementation works well, but...

You can then talk about the importance of the update operation and demo how it works.

@Desgard

This comment has been minimized.

Copy link
Contributor

Desgard commented Aug 28, 2017

I have written a article for the topic of this issue. And I will translate it to an English article recently. 😁

http://www.desgard.com/lazy-segment-tree/

@remlostime

This comment has been minimized.

Copy link
Contributor

remlostime commented Sep 9, 2017

Is there a PR for this issue? @Desgard

@Desgard

This comment has been minimized.

Copy link
Contributor

Desgard commented Sep 9, 2017

@remlostime #611

I forget to associate this issue in commit message.... sry.

@kelvinlauKL

This comment has been minimized.

Copy link
Member

kelvinlauKL commented Sep 20, 2017

Closing since we've got a PR for it already 👍

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment