Sachverhalt: A. Das Obergericht des Kantons Bern verurteilte X._ am 11. März 2008 zweitinstanzlich wegen mehrfacher sexueller Handlungen mit Kindern, mehrfacher sexueller Nötigung, mehrfacher sexueller Belästigung sowie Pornographie zu einer Freiheitsstrafe von 35 Monaten und zu einer Busse von Fr. 500.--. Es ordnete eine stationäre therapeutische Behandlung im Sinne von Art. 59 StGB an. Den Vollzug der Freiheitsstrafe schob es zugunsten der Massnahme auf. Die stationäre therapeutische Behandlung wurde in der Folge gestützt auf Art. 59 Abs. 4 StGB jeweils um drei Jahre verlängert, letztmals durch Entscheid des Regionalgerichts Bern-Mittelland vom 25. Juni 2014. Das Obergericht des Kantons Bern wies eine gegen den Entscheid vom 25. Juni 2014 erhobene Beschwerde am 30. September 2014 ab. Das Bundesgericht hiess die dagegen gerichtete Beschwerde in Strafsachen von X._ am 3. September 2015 gut, soweit es darauf eintrat, hob den obergerichtlichen Entscheid auf und wies die Sache zur neuen Beurteilung an die Vorinstanz zurück (Urteil 6B_1021/2014 vom 3. September 2015, publiziert in BGE 141 IV 396). B. Das wieder mit der Sache befasste Obergericht des Kantons Bern wies den Antrag von X._ auf Durchführung einer mündlichen Verhandlung unter Beizug des Gutachters am 11. November 2015 ab. Am 15. März 2016 wies das Obergericht die Beschwerde von X._ ab und bestätigte die durch die erste Instanz angeordnete Verlängerung der stationären therapeutischen Massnahme um drei Jahre. C. Mit Beschwerde in Strafsachen beantragt X._, es sei der Beschluss vom 15. März 2016 aufzuheben. Die Sache sei an die Vorinstanz zur Durchführung einer mündlichen Verhandlung zurückzuweisen. Eventualiter sei eine ambulante Massnahme anzuordnen und er aus der stationären Massnahme bedingt zu entlassen. Subeventualiter sei die stationäre Massnahme um zwei Jahre zu verlängern, wobei bis dahin eine ambulante Massnahme vorzubereiten sei. Die Kosten für das erst- und zweitinstanzliche kantonale Verfahren inkl. derjenigen der amtlichen Verteidigung seien dem Kanton Bern aufzuerlegen. X._ ersucht für das bundesgerichtliche Verfahren um unentgeltliche Rechtspflege und Verbeiständung. D. Das Obergericht stellt in seiner Vernehmlassung zur Beschwerde keinen Antrag. Die Generalstaatsanwaltschaft des Kantons Bern hat auf eine Stellungnahme verzichtet.