Algorithms Live: Episode 0 - Fenwick Trees

let's see all right and we're live oh hello world and welcome to algorithms live I'm Matt Fontaine I'm your host today uh joining us is Travis me uh he's a PhD candidate in Hardware security and my ICPC teamate um from the 2012 World Finals so Travis say hello hello uh so I have Travis uh as a moderator for today's broadcast and if you have any questions about anything we talk about today just feel free to type it in the chat and we'll be happy to answer it uh he'll he'll bring up up the questions as they come along um so a bit of bookkeeping before we start uh the time may vary each week uh on for the broadcast depending on what kind of guests we have that sort of thing so um please check the blog each week and pay attention to the the clock and uh we'll we'll try to keep everyone up to date um and uh the recording will be available for later viewing so if you'd like to rewatch something or um anything like that so uh this is episode zero so we're and it's going to be lecture style and we're what we're going to do is cover Fenwick trees and there are other names for Fenwick trees uh some of you may be more familiar with binary index trees uh also known as bits and it doesn't really matter which uh name you end up using uh but you could have uh one or the other for the name it it doesn't matter uh I or you you could have long political discussions about which one uh is probably a better name uh I like personally I like to switch between the two to confuse my enemies um so both both work perfectly fine um and what we're going to do is first I'm just going to explain the kind of problems that they're useful to solve uh and give you a good idea of a more basic data structure that uh that's useful in certain types of problems before going into uh the binary index tree and if you'd like to to read more about this data structure after um there's an excellent topcoder tutorial that's also available all right so so the the Baseline here is uh usually what you're we have is we're given some kind of sequence and then we're given some queries of that sequence so this is usually some sequence of integers or something like that and for each of these queries you want to determine range sums for those queries so you'll be given some range sum from A to B inclusive and you just need to report the sum of some kind uh this is fairly easy to do if you have something um so I'll just give you a sequence here so 1 4 2 1 3 five 1 2 3 maybe maybe not like that uh but I might want to know the sum in this range so the sum here is 11 and probably the easiest way to code this is just run a for loop on the sequence and query each of the array locations uh and of course in the worst case it could be the entire array so we're looking at uh order n per query which is bad uh we we'd like to be a little bit faster in most cases so what we can do is we can modify the information we have by doing some pre-computation so one trick is to compute prefix sums for uh elements in this range so we just keep a running sum in a table up to an including that point and we'll have some pre-computed information or pre uh pre-computed information and so now if we want to do the range sum what we can do is we can take the entire sum up to an including that point and subtract out the immediate predecessor it's almost like you took this entire range took a piece that you'd like to subtract off and take take this piece away and with what you're left with is just the remaining sum that you'd like to obtain um so one one problem with this so if the sequence is static this is uh not a bad technique at all but if you want to make it a little bit faster uh if we want to do it dynamically so that's uh um the dynamic solution well what we're left with is we can still get that o of one query time just by quering two elements on our table but every time we want to change some element and this is what I mean by dyamic I might want to take this element here change this to a two well now I have to recompute all these IND uh locations in my table that that's going to be fairly expensive uh so I'll say that this has o n uh recompute time so not doing very well so this is the uh motivation for uh a finwick tree what what we'd like to do is we'd like to be able to quickly solve this problem of having um prefix sums so we'd like to have a data structure that's stores information uh at various array locations and then we can easily compute a prefix sum up to an including that position uh if we can I say we only need to maintain the prefix sums because once again we can use this technique of getting the range by just subtracting out the prefix immediately before it and so that's that's our real motivation for our um Fenwick tree so I'll I'll draw out a Fenwick tree for now uh and I'll label this in binary and you'll see in a moment why this is going to be helpful and I'll go all the way up to 16 and so these are my indices in my table you can think of this as kind of an array and I'm just writing it vertically um it'll make it easier to draw and if you think of an array uh what you have in an array is every single cell is just responsible for itself so I could just draw locations like so on my array and say I'm only responsible for my location and so I'll save the sum of just my single cell a binary index tree or Fenwick tree is stored a little bit differently the odd locations are stored in that format but other locations are stored a little bit differently so we're we're going to say that uh it's organized by um the lowest one bit and it has a range of resp responsibility instead of just being responsible for its single index and we'll know exactly how far to go for how how much information it's responsible for by the lowest one bit of that number so if I take some uh Index this is six in binary and if I look at the lowest one bit that's telling me how far I have to go down to be responsible like how how much of the table am I responsible for uh so in this case I'm responsible for two indices I'll draw out uh a few range pieces of information here and so these are all the ones with lowest one bit of two where the lowest one bit of all the odd locations is just one so they're only responsible for themselves uh similarly if I I take a position like four it's responsible for four four locations and this one is as well and then we can go all the way up to eight and this table persists in this fashion and then 16 of course is responsible for the whole table if I'm only size 16 so the the key takeaway here is just realizing that uh by the lowest one bit and you'll notice and so it's uh basically each cell of this has a range of responsibility and it's going to hold its sum for that range and you'll notice that there's redundancy in this data structure uh the cell 14 for example is covered by multiple table indices so it's covered by 14 itself but it's also covered by 16 so there's some redundancy built into this data structure so if you if you maintain the prefix sums for each of these cells in this smart way uh we can actually quite simply compute uh the prefix sum and I'll show you how to do that if we look let's see 8 9 10 11 so I'll take 11 well 11 is just responsible for itself so if I drop down to the next location so it drops down to position 10 you'll notice this is responsible for a different area and if I drop down again I'm responsible for cell eight and the union of these two area or these three areas is going to be my prefix sum up to an including 11 so let let's take a look at uh what what prefix cell uh sums how those are computed so we have our prefix sums so what they'll do is they'll start at the current cell so you'll take what you're responsible for and what we'll do is we'll kind of staircase down so it kind of looks like a walking down a staircase if you go from left to right uh until no bits are left so I'll explain what that means we have we have position 11 it's responsible for itself so it has to go down to this next level so if we remove its smallest bit what we're left with is 10 well 10 is also responsible for something so I'll I'll take the two positions that it's responsible for because it's lowest one bit is two and then I'll go down to this next level which is eight and then take its sum and so you'll notice that the lowest one bit is being removed every single time as we Computing this prefix Su let's do another example let's suppose I take 14 I'll take this position remove the lowest one bit end up at this position remove the low one bit end up at this position and that will be my prefix sum for my fin tree up to an including that point so we can we can look at this and determine uh the run time here based on the number of bits that are in the run so uh so the loop runs in at most that number of bits and the maximum number of bits is going to depend on our table size which is n and there are most login bits in a number that could be on so the runtime of this step because we're removing all the bits that are currently on is O login and that's how uh the run times that compute prefix sums so you'll notice the prefix sum the runtime got worse because originally it was just o one if we were Computing it on this table but if we switch things around we actually store this in this way uh then things are a bit more complicated uh and we're we're paying a login cost on query time but what we're going to speed up is the update we're going to be able to update a single element in the Fenwick tree and uh basically um update our data structure so it holds this information so if we pull uh position let's say n you can just draw straight line to the right and see all the different uh cells that a the fenor tree must update so we have nine must get updated uh we also have that 10 must get updated and it's right here in binary I believe that's 12 and then we also have 16 and those are all the cells that must get updated in our Fenwick tree um so there are four possible uh cells that get updated what you'll notice is the lowest one bit of what gets updated so if I take my first number here this is U whoa that was weird this is nine all the lowest one bits that need to get updated are bits that are turned off in our original number and to uh to a sense this makes sense because these are the things above us that can reach us um in the way that uh this fin tree is organized so if we want to get to the next uh bit above us that can reach us which would be this position here we'll just add uh the lowest bit to that number so we we need to be able to compute this lowest one bit that's going to be extra helpful um in terms of finding that these indices but you'll notice that if I just add the lowest one bit here the bits slide over and then I add the lowest one bit to this number and they slide over again so I'm left with 1 one 0 0 and then I add the lowest one bit which is four here and I'll end up getting 16 in in binary like this so it'd be handy to be able to find the lowest one bit uh in terms of uh being able to modify things in this data structure um so if we want to find the lowest one bit in a number if we want to isolate it the easiest way to do that is just take our our position our index I and and it with the two's complement representation of I so you can get that just by taking the negative of the number anding it with I and it'll flip the appropriate bits to um to isolate just that lowest one bit so you can add it or subtract it so move up and down this table if you're in Java though there's also a really handy function in integer so you could look at integer. lowest one bit and it'll do exact the same thing and pass ni and it will actually perform this exact same operation for isolating the lowest one bit uh in our number so that that's how update works so if we want to um uh look at the update function or update position um so the goal here was we have to update all cells that own us they have ownership over us in our position and so basically everything that's close to us that has uh a bit that we don't have on is going to be one of our owners and th those are the owners that uh um we need to update again there's redundancy in this data structure so if I look at this position and I shoot this Ray to the right I can see exactly what I need to update and I can do that by uh so I can move to the next location just by adding the L one bit to the current index and you'll notice the loop is going to the number of times it runs um is the number of off bits or I should say exactly and again this is also bounded by login runtime and so that's that's the basic implementation of Fenwick tree so I'll I'll show some code for this uh just to give you an idea of how this is implemented it's rather simple to implement so what I'll do first is I'm just going to move through my indices of uh my bit so if I want to do an update remember I'm going to um be walking upward and turning on bits that are off in my original string uh so I'll know that as long as I'm in the table as long as I'm filled in the table size I can keep walking and I'll update this table position with my value change and I just need to add the lowest one bit so I'll use Java here isolate the lowest one bit of I and then move on to the next location so that's all you have to do for update it just updates a single location and then turns on lowest one bit and then for the sum I'll be going down and removing the low one bit from each of these indices or um pre-computing them so I need I need some kind of running sum it'll also work uh alternatively instead of lowest one bit I could have written it this way I and negative I and move down and of course once we have the prefix sum we can also do a range sum query uh for a given integer so this should be sum and so I can use inclusion exclusion and just call sum to find answer at that location and so uh Fenwick tree is very simple to implement they're not they're not very uh complicated not much code is involved once you get that structure correct and once you figure out how to do the updates and queries uh so now uh now what I'll be doing is discussing a handful problems uh relating to Fenwick trees uh so you can see an example of how they're used uh initially we're going to have a bit of fun I'm going to try a different style of presenting so I have uh this black background so you can all decide which uh which version you like more if you like the white background black background this might be a little easier on the eyes and I'll be discussing how uh uh a few problems involving finck trees work um so the F the first problem we'll discuss is a counting inversions problem so uh the input to this problem is some sort of of permutation and what we' like to do is we'd like to count all the inversions in this permutation know how many inversions so an inversion is just two indices that you can pick in order where the first location is greater than the second location in value that's an inversion so this is an example of an inversion in the sequence uh where 14 is an example of not an inversion uh that's actually in order uh so you could easily write an N squ algorithm that just computes um all the inversions by taking all pairs and just checking if one is less than another but we can speed this up using a Fenwick tree so what I'll do on the left is I'll just store what the uh prefix sum uh calculation looks like for the Fenwick tree so initially this table is all zeros and what I'm going to do is I'm going to sle uh sweep through indices in my Fenwick tree or uh in my sequence I have here and keep track of what's behind me and that's what's going to go in this data structure it's basically going to say for every single um value how many things are of that value behind me uh to make this calculation a little easier so initially if I'm at seven well nothing's behind me and this data structure is correct uh so I need to keep some kind of running sum of my inversions so I'll do that over here and the running sum is initially zero so I'll update this location to be one so I'll call update in my Fen tree and then I'll move on to the next location and I can query the sum Above Me by calling the Fenwick tree twice I could call the sum for the entire tree and then subtract out um six and lower and I see that I have one thing behind me so I'm basically saying I'm ending my inversion at this current location how many things behind me pair with me and so in this case it's one so I can move on to position three update my my sum table and look at everything above me again well two can pair with six and seven in form an inversion so there's two possible inversions at that location so then I update position two and move on to three in my uh my sequence also do a sum calculation and so there are also two inversions ending at three so I update my prefix sum and I move my point forward so I want the sum of one and above in my f tree so end up summing to four and I update that position move on to the second to last position in the finck tree so I end up with a one here and I want to sum everything above me so there are two things I can pair with above me and four to my left that's six and seven again so add two to my running sum the very last position is position five which also pairs with two things so I add two to my running sum so the um total running sum here is 13 so there are 13 inversions in the sequence uh the running time was quite good so for each single uh position in the array as as moving forward so there were n possible positions in that array and I did two operations I did one where I updated the position in the finwick tree that was a login operation and the second operation was a query of that position and the sum everything that's greater so my runtime of counting inversions and log in using this data structure so that's how you solve uh inversion counting problem so uh it's handy to use this with a sweep you could see how you can't do a um prefix sum technique alone because you need to be updating um elements in the fen tree so this is a good problem if you're trying to treat the Fenwick tree as a black box you can kind of think it's oh yeah it's a a method for handling Dynamic prefix sums um but sometimes you'd like to be able to peek into the data structure and actually um use some pieces of it to make things faster so our second problem uh to go over is I'll call this problem find Ki tallest so in this problem you're given a listing of heights and we'll say the heights are from 1 to 10 6 cenm so very strange problem people are very short or very tall um and the the listing could look something like this you could think of it as a table so maybe these are my Heights of people very short people and so suppose I have eight people of height one two people of height two 10 people of height three 100 people of height four one person of height five two person two people of height six uh and I'd like to find the C tallest person uh I'm actually going to mix things here I'm GNA have two types of queries so one is I could update the number of people of that height um so if I'm storring this so I'll take some height and some number so H is the height number is a sort of quantity saying and I I'll say this is plus or minus you could add people of that height or subtract people of that height from your registration there uh and the second piece is a query so you're given some value k and we'll we'll say that the number is between 1 and 10 to the 18th for our query and our goal here is we want to find the kith person so the kith tallest person so the update we'll talk about handling later uh or what what one thing we could do is we could store a Fenwick tree um for all possible Heights so it's stored over all possible Heights that's the range of the Fenwick tree so it's going to have 1006 or a million elements in the Fenwick tree um and then when we process a query we we want to find the C the CI tallest person so if if we want the 50th person we could count this real quick and realize that the 50th person is of height four we could Loop through it all at once and say Well they're eight people of height one that's not what I'm looking for uh so we could have a sum upt including that position and find the 100th person if you're apping with this problem the first solution that comes to mind is first binary searching uh back and forth over what the height will be for the CI person and then just using the Fenwick tree as a verifier to determine if that is indeed that person so maybe I'm looking for the second person I look at this position we' take the prefix sum and we'd see it's 120 well that's that's too much so we try now we're doing a binary search over this range uh and we could keep splitting this in half at every single step and then eventually end up into position one just by itself and realize the second person uh the second tallest person or second shortest person I should say um is height one and the runtime of this algorithm we'd have a login component and that's for our binary search and then we have a secondary login component and that's for querying our bit and so our runtime of this algorithm is log s n but I'd like to go faster I'll say log squ n is not good enough so this is log n Times log n this this notation right here uh for log squ n I'd like to be able to do this query because I've already got my update to log in I'd like to be able to do this fine cith query in login time so the way I'm going to do that is I'm just going to use how I organize my finwick tree so I'll draw I'll draw the full finwick tree out and we'll um once again takes I'll move this over for more space I'll show you how we can basically combine a query through the binary index tree with a binary search and be able to do this quite quickly uh so what I'll store here additionally so these are all the heights so it's one two three four five six seven8 nine 10 and I could store values here so I'll take take my values in this height so if I want to Let's draw out the binary index tree format again so I know exactly what I'm updating so let's say I update position one in my finwick tree I could um I have to put eight at one so initially everything has zero so I'm going to fill my Fen tree and then I'll show you how I do the queries quickly I have eight eight at position one eight at position two eight at position four eight at position 8 and eight at position 16 and then two at position so if I also want update position two well now everything gets updated by two I could also um add three so I want to add 10 to three so I get 10 update position 4 which is 20 update position eight so this comes up to 20 and position 16 and then I could also update position four with 100 so you can see the locations so this ends up with 120 position 8 is 120 then position 16 is also 120 uh five is going to get one so it's got a few cells to update of its own so it's all the cells that own it basically and then six is going to get an update of two so this comes up to three this comes up to three and this comes up to three and those are the cells that get updated there so you'll notice there there are a few blank cells uh the exact value of everything in the finwick tree isn't actually saved in the finwick tree it's just saving these Aggregates for the ranges so if I want to find the Ki element so let's say I want to find the 10th element this is this is the way I go about doing this I just look for large powers of two so I take the largest power of two or the largest thing with just one bit on in my table and that's going to be the first thing I'm querying and I'm basically going to do a high low search on this almost like a almost like a binary search I'll take notice that if I only have one bit on this representative is the entire prefix sum so I don't have to do a big login query I can just look at my table at the single location and I can know that the sum prefix sum at position 16 is 123 so I'll take that that prefix sum and I'll know that that's too much if I'm looking for the 20th element that's way too much so instead of looking above me which there's nothing above me on that table I'm going to look below me on that uh that prefix sum so I know I'm somewhere in this side of the table so if I take the I bit shift it right by one then I've basically look at this location position eight so this is starting to feel a little bit like a binary search I've just Swatch swap there so either my answer is going to be in 15 through n or my answer is going to be in this eight and I could quickly figure out which side uh this is on just by looking at the sum up to an including eight that's 123 that's too big I need to look uh elsewhere in my table so let let's Miss let's look at uh let's say we're looking for um position 121 because I want you to see what happens when you miss on the the wrong side so I'll take this off I'll end up looking at position four and I have two options I'm either taking the sum from Seven all the way down uh to five or it's going to be in this half I don't I don't know which half I look at 121 well that's uh the 121th person is too high so he's going to be on the upper half of my search so I can just query that position in the table and then move to the other half of my search so I'm going to retain this this number and move on to my next bit which is um two so now I'm looking in this half I'm actually looking at position six because I'm going to retain this information but I'm also going to add in the bit that I care about that I want to do my split search on and I basically have to decide so I had 120 I'm going to remove that from my search so if I'm looking for 121 when I realized it wasn't in this side of the prefix sum well I subtract 120 from it and I'm left with just one so I need to go one further on this side of the search so you'll notice this isn't an entire prefix sum but it's a sum up to that position four so I'll take a look at that I'll look at three well that's too big I need to find uh position one so I'll look in the lower half of my search and then I'll try five which is 0 one 01 and I look at this location and I see it sums to exactly one so it's very much similar to a binary search except now we're just walking this binary index tree uh every single prefix sum query that we're doing is an O of one uh so the amount of time it takes to get all the way down is the number of bits that are on in my string so my runtime is just going to be log in um by walking the binary index tree all right and so uh my my last technique I'm going to do is I'm going to show you how to do the bit back WS so instead of doing a point update and then a range query I'm going to do um a range update where I'm going to basically say what's the range from A to B inclusive and query a single position and tell me what's the that position um value at that given position so what I like to do is i' like to have a bit that works backwards I'd like for the bit to update some range so I'll say insert some range from A to B inclusive and modify it by some amount so I'll call that amount Delta and instead of doing a range query I'm just going to query a single position and tell me what the value is at that location so you don't actually have to modify your binary index tree to get this to work you can use the binary index tree as a black box almost and deter and basically have this Behavior have an ability to update range by some amount and increment all values in that range by that amount so it's almost like let's say I had a sequence like this and I say that I want all these values to go up by one so the way we're going to get this to work so that we can easily pull out elements is instead of storing information on the what we're going to do is we're going to store information based on the change in value so I'll show you how this work so initially let's say everything has value zero in the array in our sequence what I'll do is let's say I want to increment values in this range well I'll put the number one here here if I want it to go up by one at the start of my sequence and just after the end of my sequence I'll put negative one so maybe there's a few more zeros behind me so my real sequence is actually going to look like this so how do we get the value out how do we know that this position is one well this is what we do we take the prefix sum if I take the prefix sum up to an including this you'll notice that the sum goes all the way up to one but if I take the prefix sum going past that the negative one is part of my prefix sum it cancels out this initial one here so if I did a query up to this point it would come out as zero exactly as I have at this moment comes out as zero and if I query inside my interval it comes out as one if I query before my interval my prefix sum ends up being zero let's do another example we'll take uh we'll increment this location by two so I'm taking everything in this range and incrementing it by two in my real array the thing I'm actually uh peering at I'll have two a bunch of Threes then it goes back to one and so on so this is what my real array looks like so if I want to pull out this location here find out this is this three well I'll just take prefix sum up to an including that location and I run that sum it ends up giving me three if I go a bit further well this -2 cancels it out that was um being incremented my prefix sum will end up being just one and I'll pull out that number one and so you can actually do a binary index tree backwards uh if you if you'd like to know you can actually get both of them you can get both the range update and uh the range query and for that you can check out P's blog uh and he's uh if you just take a quick quick look at that if you look at one of his older posts he talks about how you can store a linear function uh in the finwick tree and actually have it work to where it um gets you both the range update and the range query which is exciting so those those are some problems uh I I have for you to just start learning finwick trees uh if you'd like to try a few problems yourself here here are a few problems I recommend if you want to go code them and so I'll pull pull this up real quick so the the first problem is a usaco problem that I really enjoy and it's called finding the median and I'll put these in the link in the video description so you can try try yourself um after but this is uh from usaco 2011 and it's the November contest and the problem is called above the median so you can try it out and solve a neat problem with fin finwick tree uh the second problem I have for you you can also submit on ctis both these locations have a online judge that you can submit on uh but on open ctis you can solve the problem movie collection and I'll put both these uh problems in the description um in the video and you you all can try try it out uh and then I'll give you a small preview for next week episode so here's my next week's preview if you don't know uh Donald's canth but every year Donald's gives this wonderful Christmas tree lecture that uh he he covers something wonderful about trees uh and just presents it before the semester comes to a close at Stanford and so we'll be giving our own Christmas tree lecture here um that that's what I have for next week we'll be exploring a few properties of trees uh and uh some some well-known properties of trees some well-known problems and at the end of the uh the episode I'll be giving you a bit of a challenging problem using some of those properties uh we'll be doing a few proofs in this lecture so you may want to review proof by contradiction uh and we'll be proving some of these properties and some of these algorithms um for finding information about trees uh so it should be fairly exciting if you if you love graph Theory so if you review a bit of graph Theory review a bit of uh proof by contradiction uh should be exciting uh for the coming week um so before I close if anyone has any questions for me about about this uh Channel or about um our show um so one of the the uh viewers uh asked why you were not coding in C++ oh that's a that's a good question uh I guess um Java is my contest language in a way um most most of us at U UCF actually code in Java uh although I do compete in Python from time to time uh especially for easier problems it's very convenient uh but I do know C++ as well it's just I I use it for other things and not not as much for competitive programming um I find it's much easier that uh copying some other competitive programmers it's much harder to make a bug in Java uh so I I code in it for the accuracy and some of the library uh usage that I like um uh on that topic uh someone might have a concern about the uh code you typed up um they think uh I I uh could you bring it up um in your range sum uh I believe you went from uh I to J but I think you needed to subtract one from your lower index oh yes this is also a bug uh but yeah okay um all right just all checking it yes so so next for the next episode if you spot a bug and you uh think you have it just type in all caps in the live chat and we'll fix right away it's actually my fault I uh I should have brought it up earlier uh but I didn't notice it until after you had already closed out the code and I'm like I I'll just bring that up at the end that's my fault um and then the last question uh that someone actually had and I thought it was kind of interesting um uh what software are you using to uh do your drawing oh right so uh I've kind of got a mix of the big tech companies here but for my drawing I'm using um Microsoft's one note uh and for of course we're using YouTube live to do the live stream so a mix of Google and Microsoft to get this to work um and did anyone have a preference uh for the white background versus the black background that would be something that'd be neat to uh discuss um uh also uh in the meantime actually uh there was another question uh do you have an interesting 2D Fenwick tree problem uh because uh someone's kind of car to like you know you know test on that type of problem all right I I'll I'll be covering the multi-dimensional Fenwick trees in a a future future episode I decided to keep things simple get us to test this format out this is uh very new for us this live talk show format but um yeah we we'll be covering a bunch of interesting stuff from week to week and hopefully we'll have some guests on soon uh that could teach some interesting things and have a conversation back and forth about uh algorithms or techniques that we find interesting so um and it seems that people prefer the uh black background um it was a four to one four for black and one for orange okay one one one for orange uh I well we'll have a bit of fun before we sign off uh I've I've learned that there's this wonderful uh pen tool for the back blackground where it's uh very colorful uh I don't I don't know uh how people feel about that one I I not entirely sure what we'll use it for but it might be fun to draw graphs in this style um but maybe not oh well so that that's all we have for our show this week uh tune in next week at the same time same day and uh we'll we'll continue on cover some interesting tree C topics so I'll see you all next week thank you Matt and got to figure out

let&#39;s see all right and we&#39;re live oh hello world and welcome to algorithms live I&#39;m Matt Fontaine I&#39;m your host today uh joining us is Travis me uh he&#39;s a PhD candidate in Hardware security and my ICPC teamate um from the 2012 World Finals so Travis say hello hello uh so I have Travis uh as a moderator for today&#39;s broadcast and if you have any questions about anything we talk about today just feel free to type it in the chat and we&#39;ll be happy to answer it uh he&#39;ll he&#39;ll bring up up the questions as they come along um so a bit of bookkeeping before we start uh the time may vary each week uh on for the broadcast depending on what kind of guests we have that sort of thing so um please check the blog each week and pay attention to the the clock and uh we&#39;ll we&#39;ll try to keep everyone up to date um and uh the recording will be available for later viewing so if you&#39;d like to rewatch something or um anything like that so uh this is episode zero so we&#39;re and it&#39;s going to be lecture style and we&#39;re what we&#39;re going to do is cover Fenwick trees and there are other names for Fenwick trees uh some of you may be more familiar with binary index trees uh also known as bits and it doesn&#39;t really matter which uh name you end up using uh but you could have uh one or the other for the name it it doesn&#39;t matter uh I or you you could have long political discussions about which one uh is probably a better name uh I like personally I like to switch between the two to confuse my enemies um so both both work perfectly fine um and what we&#39;re going to do is first I&#39;m just going to explain the kind of problems that they&#39;re useful to solve uh and give you a good idea of a more basic data structure that uh that&#39;s useful in certain types of problems before going into uh the binary index tree and if you&#39;d like to to read more about this data structure after um there&#39;s an excellent topcoder tutorial that&#39;s also available all right so so the the Baseline here is uh usually what you&#39;re we have is we&#39;re given some kind of sequence and then we&#39;re given some queries of that sequence so this is usually some sequence of integers or something like that and for each of these queries you want to determine range sums for those queries so you&#39;ll be given some range sum from A to B inclusive and you just need to report the sum of some kind uh this is fairly easy to do if you have something um so I&#39;ll just give you a sequence here so 1 4 2 1 3 five 1 2 3 maybe maybe not like that uh but I might want to know the sum in this range so the sum here is 11 and probably the easiest way to code this is just run a for loop on the sequence and query each of the array locations uh and of course in the worst case it could be the entire array so we&#39;re looking at uh order n per query which is bad uh we we&#39;d like to be a little bit faster in most cases so what we can do is we can modify the information we have by doing some pre-computation so one trick is to compute prefix sums for uh elements in this range so we just keep a running sum in a table up to an including that point and we&#39;ll have some pre-computed information or pre uh pre-computed information and so now if we want to do the range sum what we can do is we can take the entire sum up to an including that point and subtract out the immediate predecessor it&#39;s almost like you took this entire range took a piece that you&#39;d like to subtract off and take take this piece away and with what you&#39;re left with is just the remaining sum that you&#39;d like to obtain um so one one problem with this so if the sequence is static this is uh not a bad technique at all but if you want to make it a little bit faster uh if we want to do it dynamically so that&#39;s uh um the dynamic solution well what we&#39;re left with is we can still get that o of one query time just by quering two elements on our table but every time we want to change some element and this is what I mean by dyamic I might want to take this element here change this to a two well now I have to recompute all these IND uh locations in my table that that&#39;s going to be fairly expensive uh so I&#39;ll say that this has o n uh recompute time so not doing very well so this is the uh motivation for uh a finwick tree what what we&#39;d like to do is we&#39;d like to be able to quickly solve this problem of having um prefix sums so we&#39;d like to have a data structure that&#39;s stores information uh at various array locations and then we can easily compute a prefix sum up to an including that position uh if we can I say we only need to maintain the prefix sums because once again we can use this technique of getting the range by just subtracting out the prefix immediately before it and so that&#39;s that&#39;s our real motivation for our um Fenwick tree so I&#39;ll I&#39;ll draw out a Fenwick tree for now uh and I&#39;ll label this in binary and you&#39;ll see in a moment why this is going to be helpful and I&#39;ll go all the way up to 16 and so these are my indices in my table you can think of this as kind of an array and I&#39;m just writing it vertically um it&#39;ll make it easier to draw and if you think of an array uh what you have in an array is every single cell is just responsible for itself so I could just draw locations like so on my array and say I&#39;m only responsible for my location and so I&#39;ll save the sum of just my single cell a binary index tree or Fenwick tree is stored a little bit differently the odd locations are stored in that format but other locations are stored a little bit differently so we&#39;re we&#39;re going to say that uh it&#39;s organized by um the lowest one bit and it has a range of resp responsibility instead of just being responsible for its single index and we&#39;ll know exactly how far to go for how how much information it&#39;s responsible for by the lowest one bit of that number so if I take some uh Index this is six in binary and if I look at the lowest one bit that&#39;s telling me how far I have to go down to be responsible like how how much of the table am I responsible for uh so in this case I&#39;m responsible for two indices I&#39;ll draw out uh a few range pieces of information here and so these are all the ones with lowest one bit of two where the lowest one bit of all the odd locations is just one so they&#39;re only responsible for themselves uh similarly if I I take a position like four it&#39;s responsible for four four locations and this one is as well and then we can go all the way up to eight and this table persists in this fashion and then 16 of course is responsible for the whole table if I&#39;m only size 16 so the the key takeaway here is just realizing that uh by the lowest one bit and you&#39;ll notice and so it&#39;s uh basically each cell of this has a range of responsibility and it&#39;s going to hold its sum for that range and you&#39;ll notice that there&#39;s redundancy in this data structure uh the cell 14 for example is covered by multiple table indices so it&#39;s covered by 14 itself but it&#39;s also covered by 16 so there&#39;s some redundancy built into this data structure so if you if you maintain the prefix sums for each of these cells in this smart way uh we can actually quite simply compute uh the prefix sum and I&#39;ll show you how to do that if we look let&#39;s see 8 9 10 11 so I&#39;ll take 11 well 11 is just responsible for itself so if I drop down to the next location so it drops down to position 10 you&#39;ll notice this is responsible for a different area and if I drop down again I&#39;m responsible for cell eight and the union of these two area or these three areas is going to be my prefix sum up to an including 11 so let let&#39;s take a look at uh what what prefix cell uh sums how those are computed so we have our prefix sums so what they&#39;ll do is they&#39;ll start at the current cell so you&#39;ll take what you&#39;re responsible for and what we&#39;ll do is we&#39;ll kind of staircase down so it kind of looks like a walking down a staircase if you go from left to right uh until no bits are left so I&#39;ll explain what that means we have we have position 11 it&#39;s responsible for itself so it has to go down to this next level so if we remove its smallest bit what we&#39;re left with is 10 well 10 is also responsible for something so I&#39;ll I&#39;ll take the two positions that it&#39;s responsible for because it&#39;s lowest one bit is two and then I&#39;ll go down to this next level which is eight and then take its sum and so you&#39;ll notice that the lowest one bit is being removed every single time as we Computing this prefix Su let&#39;s do another example let&#39;s suppose I take 14 I&#39;ll take this position remove the lowest one bit end up at this position remove the low one bit end up at this position and that will be my prefix sum for my fin tree up to an including that point so we can we can look at this and determine uh the run time here based on the number of bits that are in the run so uh so the loop runs in at most that number of bits and the maximum number of bits is going to depend on our table size which is n and there are most login bits in a number that could be on so the runtime of this step because we&#39;re removing all the bits that are currently on is O login and that&#39;s how uh the run times that compute prefix sums so you&#39;ll notice the prefix sum the runtime got worse because originally it was just o one if we were Computing it on this table but if we switch things around we actually store this in this way uh then things are a bit more complicated uh and we&#39;re we&#39;re paying a login cost on query time but what we&#39;re going to speed up is the update we&#39;re going to be able to update a single element in the Fenwick tree and uh basically um update our data structure so it holds this information so if we pull uh position let&#39;s say n you can just draw straight line to the right and see all the different uh cells that a the fenor tree must update so we have nine must get updated uh we also have that 10 must get updated and it&#39;s right here in binary I believe that&#39;s 12 and then we also have 16 and those are all the cells that must get updated in our Fenwick tree um so there are four possible uh cells that get updated what you&#39;ll notice is the lowest one bit of what gets updated so if I take my first number here this is U whoa that was weird this is nine all the lowest one bits that need to get updated are bits that are turned off in our original number and to uh to a sense this makes sense because these are the things above us that can reach us um in the way that uh this fin tree is organized so if we want to get to the next uh bit above us that can reach us which would be this position here we&#39;ll just add uh the lowest bit to that number so we we need to be able to compute this lowest one bit that&#39;s going to be extra helpful um in terms of finding that these indices but you&#39;ll notice that if I just add the lowest one bit here the bits slide over and then I add the lowest one bit to this number and they slide over again so I&#39;m left with 1 one 0 0 and then I add the lowest one bit which is four here and I&#39;ll end up getting 16 in in binary like this so it&#39;d be handy to be able to find the lowest one bit uh in terms of uh being able to modify things in this data structure um so if we want to find the lowest one bit in a number if we want to isolate it the easiest way to do that is just take our our position our index I and and it with the two&#39;s complement representation of I so you can get that just by taking the negative of the number anding it with I and it&#39;ll flip the appropriate bits to um to isolate just that lowest one bit so you can add it or subtract it so move up and down this table if you&#39;re in Java though there&#39;s also a really handy function in integer so you could look at integer. lowest one bit and it&#39;ll do exact the same thing and pass ni and it will actually perform this exact same operation for isolating the lowest one bit uh in our number so that that&#39;s how update works so if we want to um uh look at the update function or update position um so the goal here was we have to update all cells that own us they have ownership over us in our position and so basically everything that&#39;s close to us that has uh a bit that we don&#39;t have on is going to be one of our owners and th those are the owners that uh um we need to update again there&#39;s redundancy in this data structure so if I look at this position and I shoot this Ray to the right I can see exactly what I need to update and I can do that by uh so I can move to the next location just by adding the L one bit to the current index and you&#39;ll notice the loop is going to the number of times it runs um is the number of off bits or I should say exactly and again this is also bounded by login runtime and so that&#39;s that&#39;s the basic implementation of Fenwick tree so I&#39;ll I&#39;ll show some code for this uh just to give you an idea of how this is implemented it&#39;s rather simple to implement so what I&#39;ll do first is I&#39;m just going to move through my indices of uh my bit so if I want to do an update remember I&#39;m going to um be walking upward and turning on bits that are off in my original string uh so I&#39;ll know that as long as I&#39;m in the table as long as I&#39;m filled in the table size I can keep walking and I&#39;ll update this table position with my value change and I just need to add the lowest one bit so I&#39;ll use Java here isolate the lowest one bit of I and then move on to the next location so that&#39;s all you have to do for update it just updates a single location and then turns on lowest one bit and then for the sum I&#39;ll be going down and removing the low one bit from each of these indices or um pre-computing them so I need I need some kind of running sum it&#39;ll also work uh alternatively instead of lowest one bit I could have written it this way I and negative I and move down and of course once we have the prefix sum we can also do a range sum query uh for a given integer so this should be sum and so I can use inclusion exclusion and just call sum to find answer at that location and so uh Fenwick tree is very simple to implement they&#39;re not they&#39;re not very uh complicated not much code is involved once you get that structure correct and once you figure out how to do the updates and queries uh so now uh now what I&#39;ll be doing is discussing a handful problems uh relating to Fenwick trees uh so you can see an example of how they&#39;re used uh initially we&#39;re going to have a bit of fun I&#39;m going to try a different style of presenting so I have uh this black background so you can all decide which uh which version you like more if you like the white background black background this might be a little easier on the eyes and I&#39;ll be discussing how uh uh a few problems involving finck trees work um so the F the first problem we&#39;ll discuss is a counting inversions problem so uh the input to this problem is some sort of of permutation and what we&#39; like to do is we&#39;d like to count all the inversions in this permutation know how many inversions so an inversion is just two indices that you can pick in order where the first location is greater than the second location in value that&#39;s an inversion so this is an example of an inversion in the sequence uh where 14 is an example of not an inversion uh that&#39;s actually in order uh so you could easily write an N squ algorithm that just computes um all the inversions by taking all pairs and just checking if one is less than another but we can speed this up using a Fenwick tree so what I&#39;ll do on the left is I&#39;ll just store what the uh prefix sum uh calculation looks like for the Fenwick tree so initially this table is all zeros and what I&#39;m going to do is I&#39;m going to sle uh sweep through indices in my Fenwick tree or uh in my sequence I have here and keep track of what&#39;s behind me and that&#39;s what&#39;s going to go in this data structure it&#39;s basically going to say for every single um value how many things are of that value behind me uh to make this calculation a little easier so initially if I&#39;m at seven well nothing&#39;s behind me and this data structure is correct uh so I need to keep some kind of running sum of my inversions so I&#39;ll do that over here and the running sum is initially zero so I&#39;ll update this location to be one so I&#39;ll call update in my Fen tree and then I&#39;ll move on to the next location and I can query the sum Above Me by calling the Fenwick tree twice I could call the sum for the entire tree and then subtract out um six and lower and I see that I have one thing behind me so I&#39;m basically saying I&#39;m ending my inversion at this current location how many things behind me pair with me and so in this case it&#39;s one so I can move on to position three update my my sum table and look at everything above me again well two can pair with six and seven in form an inversion so there&#39;s two possible inversions at that location so then I update position two and move on to three in my uh my sequence also do a sum calculation and so there are also two inversions ending at three so I update my prefix sum and I move my point forward so I want the sum of one and above in my f tree so end up summing to four and I update that position move on to the second to last position in the finck tree so I end up with a one here and I want to sum everything above me so there are two things I can pair with above me and four to my left that&#39;s six and seven again so add two to my running sum the very last position is position five which also pairs with two things so I add two to my running sum so the um total running sum here is 13 so there are 13 inversions in the sequence uh the running time was quite good so for each single uh position in the array as as moving forward so there were n possible positions in that array and I did two operations I did one where I updated the position in the finwick tree that was a login operation and the second operation was a query of that position and the sum everything that&#39;s greater so my runtime of counting inversions and log in using this data structure so that&#39;s how you solve uh inversion counting problem so uh it&#39;s handy to use this with a sweep you could see how you can&#39;t do a um prefix sum technique alone because you need to be updating um elements in the fen tree so this is a good problem if you&#39;re trying to treat the Fenwick tree as a black box you can kind of think it&#39;s oh yeah it&#39;s a a method for handling Dynamic prefix sums um but sometimes you&#39;d like to be able to peek into the data structure and actually um use some pieces of it to make things faster so our second problem uh to go over is I&#39;ll call this problem find Ki tallest so in this problem you&#39;re given a listing of heights and we&#39;ll say the heights are from 1 to 10 6 cenm so very strange problem people are very short or very tall um and the the listing could look something like this you could think of it as a table so maybe these are my Heights of people very short people and so suppose I have eight people of height one two people of height two 10 people of height three 100 people of height four one person of height five two person two people of height six uh and I&#39;d like to find the C tallest person uh I&#39;m actually going to mix things here I&#39;m GNA have two types of queries so one is I could update the number of people of that height um so if I&#39;m storring this so I&#39;ll take some height and some number so H is the height number is a sort of quantity saying and I I&#39;ll say this is plus or minus you could add people of that height or subtract people of that height from your registration there uh and the second piece is a query so you&#39;re given some value k and we&#39;ll we&#39;ll say that the number is between 1 and 10 to the 18th for our query and our goal here is we want to find the kith person so the kith tallest person so the update we&#39;ll talk about handling later uh or what what one thing we could do is we could store a Fenwick tree um for all possible Heights so it&#39;s stored over all possible Heights that&#39;s the range of the Fenwick tree so it&#39;s going to have 1006 or a million elements in the Fenwick tree um and then when we process a query we we want to find the C the CI tallest person so if if we want the 50th person we could count this real quick and realize that the 50th person is of height four we could Loop through it all at once and say Well they&#39;re eight people of height one that&#39;s not what I&#39;m looking for uh so we could have a sum upt including that position and find the 100th person if you&#39;re apping with this problem the first solution that comes to mind is first binary searching uh back and forth over what the height will be for the CI person and then just using the Fenwick tree as a verifier to determine if that is indeed that person so maybe I&#39;m looking for the second person I look at this position we&#39; take the prefix sum and we&#39;d see it&#39;s 120 well that&#39;s that&#39;s too much so we try now we&#39;re doing a binary search over this range uh and we could keep splitting this in half at every single step and then eventually end up into position one just by itself and realize the second person uh the second tallest person or second shortest person I should say um is height one and the runtime of this algorithm we&#39;d have a login component and that&#39;s for our binary search and then we have a secondary login component and that&#39;s for querying our bit and so our runtime of this algorithm is log s n but I&#39;d like to go faster I&#39;ll say log squ n is not good enough so this is log n Times log n this this notation right here uh for log squ n I&#39;d like to be able to do this query because I&#39;ve already got my update to log in I&#39;d like to be able to do this fine cith query in login time so the way I&#39;m going to do that is I&#39;m just going to use how I organize my finwick tree so I&#39;ll draw I&#39;ll draw the full finwick tree out and we&#39;ll um once again takes I&#39;ll move this over for more space I&#39;ll show you how we can basically combine a query through the binary index tree with a binary search and be able to do this quite quickly uh so what I&#39;ll store here additionally so these are all the heights so it&#39;s one two three four five six seven8 nine 10 and I could store values here so I&#39;ll take take my values in this height so if I want to Let&#39;s draw out the binary index tree format again so I know exactly what I&#39;m updating so let&#39;s say I update position one in my finwick tree I could um I have to put eight at one so initially everything has zero so I&#39;m going to fill my Fen tree and then I&#39;ll show you how I do the queries quickly I have eight eight at position one eight at position two eight at position four eight at position 8 and eight at position 16 and then two at position so if I also want update position two well now everything gets updated by two I could also um add three so I want to add 10 to three so I get 10 update position 4 which is 20 update position eight so this comes up to 20 and position 16 and then I could also update position four with 100 so you can see the locations so this ends up with 120 position 8 is 120 then position 16 is also 120 uh five is going to get one so it&#39;s got a few cells to update of its own so it&#39;s all the cells that own it basically and then six is going to get an update of two so this comes up to three this comes up to three and this comes up to three and those are the cells that get updated there so you&#39;ll notice there there are a few blank cells uh the exact value of everything in the finwick tree isn&#39;t actually saved in the finwick tree it&#39;s just saving these Aggregates for the ranges so if I want to find the Ki element so let&#39;s say I want to find the 10th element this is this is the way I go about doing this I just look for large powers of two so I take the largest power of two or the largest thing with just one bit on in my table and that&#39;s going to be the first thing I&#39;m querying and I&#39;m basically going to do a high low search on this almost like a almost like a binary search I&#39;ll take notice that if I only have one bit on this representative is the entire prefix sum so I don&#39;t have to do a big login query I can just look at my table at the single location and I can know that the sum prefix sum at position 16 is 123 so I&#39;ll take that that prefix sum and I&#39;ll know that that&#39;s too much if I&#39;m looking for the 20th element that&#39;s way too much so instead of looking above me which there&#39;s nothing above me on that table I&#39;m going to look below me on that uh that prefix sum so I know I&#39;m somewhere in this side of the table so if I take the I bit shift it right by one then I&#39;ve basically look at this location position eight so this is starting to feel a little bit like a binary search I&#39;ve just Swatch swap there so either my answer is going to be in 15 through n or my answer is going to be in this eight and I could quickly figure out which side uh this is on just by looking at the sum up to an including eight that&#39;s 123 that&#39;s too big I need to look uh elsewhere in my table so let let&#39;s Miss let&#39;s look at uh let&#39;s say we&#39;re looking for um position 121 because I want you to see what happens when you miss on the the wrong side so I&#39;ll take this off I&#39;ll end up looking at position four and I have two options I&#39;m either taking the sum from Seven all the way down uh to five or it&#39;s going to be in this half I don&#39;t I don&#39;t know which half I look at 121 well that&#39;s uh the 121th person is too high so he&#39;s going to be on the upper half of my search so I can just query that position in the table and then move to the other half of my search so I&#39;m going to retain this this number and move on to my next bit which is um two so now I&#39;m looking in this half I&#39;m actually looking at position six because I&#39;m going to retain this information but I&#39;m also going to add in the bit that I care about that I want to do my split search on and I basically have to decide so I had 120 I&#39;m going to remove that from my search so if I&#39;m looking for 121 when I realized it wasn&#39;t in this side of the prefix sum well I subtract 120 from it and I&#39;m left with just one so I need to go one further on this side of the search so you&#39;ll notice this isn&#39;t an entire prefix sum but it&#39;s a sum up to that position four so I&#39;ll take a look at that I&#39;ll look at three well that&#39;s too big I need to find uh position one so I&#39;ll look in the lower half of my search and then I&#39;ll try five which is 0 one 01 and I look at this location and I see it sums to exactly one so it&#39;s very much similar to a binary search except now we&#39;re just walking this binary index tree uh every single prefix sum query that we&#39;re doing is an O of one uh so the amount of time it takes to get all the way down is the number of bits that are on in my string so my runtime is just going to be log in um by walking the binary index tree all right and so uh my my last technique I&#39;m going to do is I&#39;m going to show you how to do the bit back WS so instead of doing a point update and then a range query I&#39;m going to do um a range update where I&#39;m going to basically say what&#39;s the range from A to B inclusive and query a single position and tell me what&#39;s the that position um value at that given position so what I like to do is i&#39; like to have a bit that works backwards I&#39;d like for the bit to update some range so I&#39;ll say insert some range from A to B inclusive and modify it by some amount so I&#39;ll call that amount Delta and instead of doing a range query I&#39;m just going to query a single position and tell me what the value is at that location so you don&#39;t actually have to modify your binary index tree to get this to work you can use the binary index tree as a black box almost and deter and basically have this Behavior have an ability to update range by some amount and increment all values in that range by that amount so it&#39;s almost like let&#39;s say I had a sequence like this and I say that I want all these values to go up by one so the way we&#39;re going to get this to work so that we can easily pull out elements is instead of storing information on the what we&#39;re going to do is we&#39;re going to store information based on the change in value so I&#39;ll show you how this work so initially let&#39;s say everything has value zero in the array in our sequence what I&#39;ll do is let&#39;s say I want to increment values in this range well I&#39;ll put the number one here here if I want it to go up by one at the start of my sequence and just after the end of my sequence I&#39;ll put negative one so maybe there&#39;s a few more zeros behind me so my real sequence is actually going to look like this so how do we get the value out how do we know that this position is one well this is what we do we take the prefix sum if I take the prefix sum up to an including this you&#39;ll notice that the sum goes all the way up to one but if I take the prefix sum going past that the negative one is part of my prefix sum it cancels out this initial one here so if I did a query up to this point it would come out as zero exactly as I have at this moment comes out as zero and if I query inside my interval it comes out as one if I query before my interval my prefix sum ends up being zero let&#39;s do another example we&#39;ll take uh we&#39;ll increment this location by two so I&#39;m taking everything in this range and incrementing it by two in my real array the thing I&#39;m actually uh peering at I&#39;ll have two a bunch of Threes then it goes back to one and so on so this is what my real array looks like so if I want to pull out this location here find out this is this three well I&#39;ll just take prefix sum up to an including that location and I run that sum it ends up giving me three if I go a bit further well this -2 cancels it out that was um being incremented my prefix sum will end up being just one and I&#39;ll pull out that number one and so you can actually do a binary index tree backwards uh if you if you&#39;d like to know you can actually get both of them you can get both the range update and uh the range query and for that you can check out P&#39;s blog uh and he&#39;s uh if you just take a quick quick look at that if you look at one of his older posts he talks about how you can store a linear function uh in the finwick tree and actually have it work to where it um gets you both the range update and the range query which is exciting so those those are some problems uh I I have for you to just start learning finwick trees uh if you&#39;d like to try a few problems yourself here here are a few problems I recommend if you want to go code them and so I&#39;ll pull pull this up real quick so the the first problem is a usaco problem that I really enjoy and it&#39;s called finding the median and I&#39;ll put these in the link in the video description so you can try try yourself um after but this is uh from usaco 2011 and it&#39;s the November contest and the problem is called above the median so you can try it out and solve a neat problem with fin finwick tree uh the second problem I have for you you can also submit on ctis both these locations have a online judge that you can submit on uh but on open ctis you can solve the problem movie collection and I&#39;ll put both these uh problems in the description um in the video and you you all can try try it out uh and then I&#39;ll give you a small preview for next week episode so here&#39;s my next week&#39;s preview if you don&#39;t know uh Donald&#39;s canth but every year Donald&#39;s gives this wonderful Christmas tree lecture that uh he he covers something wonderful about trees uh and just presents it before the semester comes to a close at Stanford and so we&#39;ll be giving our own Christmas tree lecture here um that that&#39;s what I have for next week we&#39;ll be exploring a few properties of trees uh and uh some some well-known properties of trees some well-known problems and at the end of the uh the episode I&#39;ll be giving you a bit of a challenging problem using some of those properties uh we&#39;ll be doing a few proofs in this lecture so you may want to review proof by contradiction uh and we&#39;ll be proving some of these properties and some of these algorithms um for finding information about trees uh so it should be fairly exciting if you if you love graph Theory so if you review a bit of graph Theory review a bit of uh proof by contradiction uh should be exciting uh for the coming week um so before I close if anyone has any questions for me about about this uh Channel or about um our show um so one of the the uh viewers uh asked why you were not coding in C++ oh that&#39;s a that&#39;s a good question uh I guess um Java is my contest language in a way um most most of us at U UCF actually code in Java uh although I do compete in Python from time to time uh especially for easier problems it&#39;s very convenient uh but I do know C++ as well it&#39;s just I I use it for other things and not not as much for competitive programming um I find it&#39;s much easier that uh copying some other competitive programmers it&#39;s much harder to make a bug in Java uh so I I code in it for the accuracy and some of the library uh usage that I like um uh on that topic uh someone might have a concern about the uh code you typed up um they think uh I I uh could you bring it up um in your range sum uh I believe you went from uh I to J but I think you needed to subtract one from your lower index oh yes this is also a bug uh but yeah okay um all right just all checking it yes so so next for the next episode if you spot a bug and you uh think you have it just type in all caps in the live chat and we&#39;ll fix right away it&#39;s actually my fault I uh I should have brought it up earlier uh but I didn&#39;t notice it until after you had already closed out the code and I&#39;m like I I&#39;ll just bring that up at the end that&#39;s my fault um and then the last question uh that someone actually had and I thought it was kind of interesting um uh what software are you using to uh do your drawing oh right so uh I&#39;ve kind of got a mix of the big tech companies here but for my drawing I&#39;m using um Microsoft&#39;s one note uh and for of course we&#39;re using YouTube live to do the live stream so a mix of Google and Microsoft to get this to work um and did anyone have a preference uh for the white background versus the black background that would be something that&#39;d be neat to uh discuss um uh also uh in the meantime actually uh there was another question uh do you have an interesting 2D Fenwick tree problem uh because uh someone&#39;s kind of car to like you know you know test on that type of problem all right I I&#39;ll I&#39;ll be covering the multi-dimensional Fenwick trees in a a future future episode I decided to keep things simple get us to test this format out this is uh very new for us this live talk show format but um yeah we we&#39;ll be covering a bunch of interesting stuff from week to week and hopefully we&#39;ll have some guests on soon uh that could teach some interesting things and have a conversation back and forth about uh algorithms or techniques that we find interesting so um and it seems that people prefer the uh black background um it was a four to one four for black and one for orange okay one one one for orange uh I well we&#39;ll have a bit of fun before we sign off uh I&#39;ve I&#39;ve learned that there&#39;s this wonderful uh pen tool for the back blackground where it&#39;s uh very colorful uh I don&#39;t I don&#39;t know uh how people feel about that one I I not entirely sure what we&#39;ll use it for but it might be fun to draw graphs in this style um but maybe not oh well so that that&#39;s all we have for our show this week uh tune in next week at the same time same day and uh we&#39;ll we&#39;ll continue on cover some interesting tree C topics so I&#39;ll see you all next week thank you Matt and got to figure out

Transcript for:Algorithms Live: Episode 0 - Fenwick Trees

Transcript for:
Algorithms Live: Episode 0 - Fenwick Trees