Over last few years number of standard algorithms and structures (dfs, FFT, segment tree, suffix automaton, ... Gomory-Hu tree) didn't change much, at least in my perception. Most of fresh tasks require pure creativity (tasks on atcoder.jp being most prominent example) or unusual combination of well-known blocks. Some tasks are even pure combinatorics math problems (I'm a big fan of these).
But I think there still are room to bring some new "primitive" structures. Let's form a list of interesting stuff that are unpopular or unknown!
My first thoughts are palindromic tree and multipoint evaluation (computes values of polynomial of degree n in n points in time).