9. Augmentation: Range Trees
Vložit
- čas přidán 3. 03. 2016
- MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: ocw.mit.edu/6-046JS15
Instructor: Erik Demaine
In this lecture, Professor Demaine covers the augmentation of data structures, updating common structures to store additional information.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
Range trees start at 59:07
Thank you kind youtube user
that's fun...
thanks.
a pure demonstration of love
thank you
i implemented the range tree exactly as he detailed, so for those of you planning to do the same, he doesn't mention some edge cases when finding nodes within the range. (1) in particular when you find a max and min node, they could be the same, or one could be an ancestor of the other (i.e. in the same tree). (2) you need to investigate the right tree of the min node and the left tree of the max node... there are a few other things that i may have forgotten. the lecture is a good place to start though!
Erik DA MAN!!!
I think the discription of finger tree as one with values stored in the leaves, internal nodes associative operation ( concatenation is string addition ie associative) lend itself to Merkle Trees, has anyone worked on this idea before???
For the search he completed at min50, we could keep max&min indices as well
+ we could search&del/ins the whole block UTXOs at once or in groups,... etc ( the details subject to brainstorming, the point is whenever we visit an interval let's check+ins+del all what's in our pocket/portfolio for it in one time)
.
I think this was the intuition behind Verkle Trees, where Kate Commitments are the associative function
i bet he is using that neat japanese chalk :)
The way they go through it, there's probably not enough Hagoromo produced anymore to keep them supplied. It's probably the plain ol' Dixon railroad chalk you can find on Amazon-bought in bulk. I'm going to get some when my Sargent dustless (pretty good brand) is used up.
anyone else have a man crush on erik...
you are not alone my friend.
Yes no help!
czcams.com/video/xVka6z1hu-I/video.html err, successor in BBST is O(1) amortized actually (that is when you have pointer to a node and you're looking for the next one and you have parent pointers)
Now just a hunch, not completely thought about yet, orthogonal searching could correspond to AMM intervals ...
1d is the slippage of 1coin, 2D is the regular xy=k EQ when it becomes a moving window
Then 3D if we want to relate 3 currencies together,...etc
amazing.. thanks a lot from India
did he throw a freesbee at 21:47 ?? lmao WHAT
슈퍼마리오 간지
Why are they using blackboards with chalk? Can't they switch to whiteboards with markers????
Those blackboards are paid and still work just fine. Why change? ;)
@@zsoltbr chalk dust are not good for health
@@zsoltbrasthma?
I want a blackboard now.
tsakalidis does this better. #ceidelitist
shut up
With all due respect you should start monetizing your videos that will also help you
MIT has an endownment $16.53 billion. Don't think they need to monetize their videos.
@@yicheng1991 5 second ads generally??
@@abhishektyagi4428 YT is going to keep including more and longer and un-ignorable ads until we all start giving them $70/mo or whatever the charge is. It's their business model: monetize unnecessary annoyance; getting money from advertisers too is just gravy. Don't for a moment think the ad situation isn't going to get worse: this is the new cable, and we all hate cable
@@chatGPT7 Yepp, these videos have already been paid by the students' tuition fees. Nevertheless, OCW is but a long ad for MIT itself.