If you have a complicated, deeply interconnected model, updating immutable data structures properly doesn't seem much easier than properly implementing shouldComponentUpdate().
You could use a lens to make the programming easier, and the logarithmic depth property of DOM-like trees makes it likely that allocation will also not be a problem.
Is it not easy because the syntax is cumbersome (eg. chained calls to setIn([...]) in immutable.js), or because it is fundamentally difficult? The former is something that's specific to Immutable.js and many other javascript frameworks. Other languages have solved that problem rather elegantly (cursors, lenses). If it's the later then I doubt shouldComponentUpdate will be much less complex than the state update function (in terms of complexity, lines of code, easy of understanding etc).