11 = (1+2+3+4+5) - (1+2+3) + (6) - (4)

Mathematica, 79 bytes

Min[2#/(d=Divisors@#~Cases~_?OddQ)+d]-2⌊(2#)^.5+.5⌋+⌈Sqrt[8#+1]~Mod~1⌉&

Explanation

I couldn't be bothered to implement the algorithm in the challenge, so I wanted to look for a shortcut to the solution. While I found one, unfortunately it doesn't beat the Mathematica answer that does implement the algorithm. That said, I'm sure this isn't optimally golfed yet, and there might be other languages who can benefit from this approach or some of the insights gained in the process.

So I claim that the sequence we're supposed to compute is:

f(n) = 2*(A212652(n) - A002024(n)) + 1 + A023532(n-1)

Alternatively, it's f(n) = 1 if n is a triangular number and f(n) = 2*(A212652(n) - A002024(n) + 1) otherwise.

In the first expression, A023532 simply encodes these two different cases. The other two sequences (plus 1) are the difference between the the largest integer k in the longest decomposition of n into consecutive integers (k-i+1) + (k-i+2) + ... + k = n and the largest integer j so that 1 + 2 + ... + j < n.

In somewhat simpler words, here is how we find the answer for non-triangular numbers: first, find the largest triangular number T_j which is less than n. Then j is the penultimate integer that gets added during step 1 (because after adding j+1 we will have exceeded n). Then decompose n into as many (or as small) consecutive integers as possible and call the maximum among these numbers k. The result is simply 2*(k-j). The intuitive reason for this is that the maximum in the decomposition grows by 1 every other step and we stop when we reach k.

We need to show four things to prove that this works:

1. f(n) = 1 for triangular numbers. This is trivially the case, because the first step simply iterates through all triangular numbers. If we hit n exactly during this process we're done and there was only one step to compute.
2. For all other numbers, we always end after a deletion step, never after an insertion step. That means all other f(n) are even.
3. In each insertion step after the first, we only add a single number. This guarantees that we'll reach a decomposition including k after k-j pairs of steps.
4. The final decomposition of n that we obtain is always the longest possible decomposition of n into consecutive integers, or in other words, it's always the decomposition of n with the lowest maximum among the summed numbers. In other words, the last number we add to the sum is always A212652(n).

We've already shown why (1) is true. Next, we prove that we can't end on an insertion step except the initial one (which doesn't happen for non-triangular numbers).

Suppose we ended on an insertion step, reaching n after adding a value p to the sum. That means that before this insertion step, the value was n-p (or less if we added multiple values at once). But this insertion step was preceded by a deletion step (since we couldn't have hit n during step 1). The last value q we removed during this deletion step was necessarily less than p due to the way the algorithm works. But that means before we removed q we had n-p+q (or less) which is less than n. But that's a contradiction, because we would have had to stop removing integers when we hit n-p+q instead of removing another q. This proves point (2) above. So now we know that we always end on a deletion step and that therefore all non-triangular numbers have even outputs.

Next we prove (3), that each insertion step can only insert one value. This is essentially a corollary of (2). We have shown that after adding one value we cannot hit n exactly and since the prove was using an inequality, we also cannot end up below n (since then n-p+q would still be less than n and we shouldn't have removed that many values in the first place). So whenever we add a single value, we're guaranteed to exceed n because we went below n by removing a smaller value. Hence, we know that the upper end of the sum grows by 1 every other step. We know the initial value of this upper end (it's the smallest m such that T_m > n). Now we just need to figure out this upper end once we've reached the final sum. Then the number of steps is simply twice the difference (plus 1).

To do this, we prove (4), that the final sum is always the decomposition of n into as many integers as possible, or the decomposition where the maximum in that decomposition is minimal (i.e. it's the earliest possible decomposition). We'll again do this by contradiction (the wording in this part could be a bit more rigorous, but I've already spent way too much time on this...).

Say the earliest/longest possible decomposition of n is some a + (a+1) + ... (b-1) + b, a ≤ b, and say the algorithm skips it. That means at the time that b gets added, a must no longer be part of the sum. If a was part of the sum s, then we'd have n ≤ s at that moment. So either the sum only contains the values from a to b, which equals n and we stop (hence we didn't skip this decomposition), or there is at least one value less than a in the sum, win which case n < s and that value would get removed until we hit the exact sum (again, the decomposition wasn't skipped). So we'd have to get rid of a before adding b. But that means we'd have to reach a situation in which a is the smallest component of the sum, and the largest isn't b yet. However, at that point we can't remove a, because the sum is clearly less than n (since b is missing), so we're required to add values first until we add b and hit n exactly. This proves (4).

So taking these things together: we know that the first pair of steps gives us a maximum value of A002024(n). We know that the maximum value of the final decomposition is A212652(n). And we know that this maximum is incremented once in every pair of steps. Hence, the final expression is 2*(A212652(n) - A002024(n) + 1). This formula almost works for triangular numbers, except that for those we only need 1 step instead of 2, which is why we correct the result with the indicator function of the triangular numbers (or its inverse, whichever is more convenient).

Finally, as for the implementation. For the former sequence, I'm using the formula MIN(odd d|n; n/d + (d-1)/2) from OEIS. It turns out to save a few bytes if we take the factor of 2 into this expression to get MIN(odd d|n; 2n/d + d-1), because that -1 then cancels with the +1 in my first version of f(n) which directly encodes the two cases for triangular and non-triangular numbers. In the code, this is:

Min[2#/(d=Divisors@#~Cases~_?OddQ)+d]

For the latter sequence (1, 2, 2, 3, 3, 3, ...), we can use a simple closed form:

⌊(2#)^.5+.5⌋

And finally, the inverse indicator function of the triangular numbers is 0 whenever 8n+1 is a perfect square. This can be expressed in Mathematica as

⌈Sqrt[8#+1]~Mod~1⌉

There are a lot of ways to express these last two sequences and to shift some constant offset between them, so I'm sure this is not an optimal implementation yet, but I hope this might give others a starting point to look into new approaches in their own languages.

Since I went to all this trouble, here is a plot of the sequence up to n = 1000 (I could also compute 100k in a couple of seconds, but it doesn't really show any additional insights):

It might be interesting to look into the variations about those very straight lines, but I'll leave that to someone else...

Mathematica, 72 bytes

(For[l=u=c=k=0,k!=#,c++,If[#>k,While[#>k,k+=++u],While[#<k,k-=l++]]];c)&

Pure function taking an integer argument.

How it works

For[ ... ]

A For loop.

l=u=c=k=0

Initialization; set l (lower), u (upper), c (counter), and k (sum) to 0.

k!=#

Condition; repeat while k is not equal to the input.

c++

Increment; increment the counter c.

If[#>k,For[,#>k,,k+=++u],For[,#<k,,k-=l++]]

Body

If[#>k, ... ]

If the input is greater than k:

While[#>k,k+=++u]

While the input is greater than k, increment u and increment k by u.

If the input is not greater than k:

While[#<k,k-=l++]

While the input is less than k, decrement k by l and increment l.

( ... ;c)

Return c after the loop.

Jelly, 29 31 28 bytes

-3 thanks to caird coinheringaahing (save a $, use the newer Ä, and use the newer Ƒ)

ÆDµ’H+ṚḞƑƇṂ
>TḢ_@Ç}‘Ḥ
RÄðċȯç

A monadic link that returns the result (N=65536 takes less than two seconds).

Try it online!

How?

For a thorough explanation of the algorithm see the fantastic post by Martin Ender.

ÆDµ’H+ṚḞƑƇṂ - Link 1, smallest natural number, M, that satisfies the below*, N
            - * N = T(M) - T(i) for some non-negative integer i <= M
ÆD          - divisors of N
  µ         - monadic chain separation, call that d
   ’        - increment d (vectorises)
    H       - halve (vectorises
      Ṛ     - reverse d
     +      - add (vectorises)
         Ƈ  - filter keep if:
        Ƒ   -   is invariant under:
       Ḟ    -     floor (i.e. those which are the result of even divisors)
          Ṃ - minimum

>TḢ_@Ç}‘Ḥ - Link 2, evaluate result for non-triangular: list of T(1) to T(N), N
>         - T(i) > N
 T        - truthy indexes
  Ḣ       - head (yields the first i for which T(i) > N)
     Ç}   - call last link (1) as a monad converted to a dyad using the right argument
   _@     - subtract with reverse @rguments
       ‘  - increment
        Ḥ - double 

RÄðċȯç - Main link: N
R      - range -> [1,2,...,N]
 Ä     - reduce with addition -> [1,3,6,10,...T(N)]
  ð    - dyadic chain separation, call that t
   ċ   - count occurrences of N in t (1 if N is triangular else 0)
     ç - call last link (2) as a dyad(t, N)
    ȯ  - or

---

The 29 byte full-program implementation I created of the algorithm described takes 4 min 30 for N=65536 on my laptop, so I suppose it does not count.

Ṁ‘ṭµS<³µ¿
ḊµS>³µ¿
0®Ḃ‘©¤ĿÐĿL’