| >+[->,[------------------------------------------------<<[->+<]>[-<++++++++++>]>[-<<+>>]<+>]<][-]< |
| package com.sk.bot; | |
| import java.io.UnsupportedEncodingException; | |
| import java.net.URLEncoder; | |
| import java.util.AbstractCollection; | |
| import java.util.Collection; | |
| import java.util.HashMap; | |
| import java.util.Iterator; | |
| import java.util.LinkedHashMap; | |
| import java.util.List; |
| (function() { | |
| var form = document.querySelector('form[name=activity_select_form]') | |
| var matches = document.location.href.match(/\/bids\/([0-9]*)/) | |
| if (form && matches[1]) { | |
| form.innerHTML += '<input type="hidden" name="bid" value="' + matches[1] + '" />' | |
| form.action = 'https://iodine.tjhsst.edu/api/eighth/signup_activity' | |
| form.target = '_blank' | |
| form.addEventListener('submit', setTimeout.bind(null, window.history.back.bind(window.history), 1000)) | |
| document.querySelector('div.blurb').innerHTML += ' API Signup enabled.' | |
| } |
We want to have a data structure that allows us to do two things
f(a[i], ..., a[j]) for i <= j (the query)a[i] = v for some i (the update)Naively, one could do this in such a way that either the query or the update is O(1) and the other is O(n). The most basic method would be to simply store a[i] and then for the query, simply compute the function in O(n). However, that will obviously not be good enough for practical applications.
| <h1 id="binary-indexed-trees-and-segment-trees">Binary Indexed Trees and Segment Trees</h1> | |
| <h2 id="the-problem">The Problem</h2> | |
| <p>We want to have a data structure that allows us to do two things</p> | |
| <ol> | |
| <li>Make queries of the form <code>f(a[i], ..., a[j])</code> for <code>i <= j</code> (the <strong>query</strong>)</li> | |
| <li>Update <code>a[i] = v</code> for some <code>i</code> (the <strong>update</strong>)</li> | |
| </ol> | |
| <p>Naively, one could do this in such a way that either the query or the update is <code>O(1)</code> and the other is <code>O(n)</code>. The most basic method would be to simply store <code>a[i]</code> and then for the query, simply compute the function in <code>O(n)</code>. However, that will obviously not be good enough for practical applications. </p> | |
| <h2 id="segment-trees">Segment Trees</h2> | |
| <p>Segment trees provide a way to efficiently and easily perform both the query and the update in <code>O(log n)</code>. The key to how this works is that the cumulative totals are stored in a tree |
| while True: | |
| cmd = raw_input() | |
| noprint =False | |
| noexec =False | |
| if cmd[0]=='x': | |
| noprint=True | |
| if cmd[0]=='p': | |
| noexec=True | |
| if not noexec: |
| <!DOCTYPE html> | |
| <html> | |
| <head> | |
| <meta charset="utf-8"> | |
| <title>JS Bin</title> | |
| <script src="http://cdnjs.cloudflare.com/ajax/libs/mathjs/1.2.0/math.js"></script> | |
| <style id="jsbin-css"> | |
| #source { | |
| display: none; | |
| } |
The basic steps are listed below. They are described in more detail afterwards.
When doing work, always make sure to update and checkout a new branch. This way, we keep the main branch clean.
| import java.util.ArrayList; | |
| import java.util.HashMap; | |
| import java.util.Iterator; | |
| import java.util.List; | |
| import java.util.ListIterator; | |
| import java.util.Map; | |
| import java.util.Map.Entry; | |
| public class JSONUtil { |
| import java.io.ByteArrayOutputStream; | |
| import java.io.IOException; | |
| import java.io.InputStream; | |
| import java.io.UnsupportedEncodingException; | |
| import java.net.HttpURLConnection; | |
| import java.net.URL; | |
| import java.net.URLEncoder; | |
| import java.util.HashMap; | |
| import java.util.Map; | |
| import java.util.concurrent.ConcurrentHashMap; |