We study the general integer programming (IP) problem of optimizing a separable convex function over the integer points of a polytope: \(\min \{f({\textbf{x}}) \mid A{\textbf{x}}= {\textbf{b}}, \, {\textbf{l}}\le {\textbf{x}}\le {\textbf{u}}, \, {\textbf{x}}\in \mathbb {Z}^n\}\) . The number of variables n is a variable part of the input, and we consider the regime where the constraint matrix A has small coefficients \(\Vert A\Vert _\infty \) and small primal or dual treedepth \({{\,\mathrm{\textrm{td}}\,}}_P(A)\) or \({{\,\mathrm{\textrm{td}}\,}}_D(A)\) , respectively. Equivalently, we consider block-structured matrices, in particular n-fold, tree-fold, 2-stage and multi-stage matrices. We ask about the possibility of near-linear algorithms in the general case of (non-linear) separable convex functions. The techniques of previous works for the linear case are inherently limited to it; in fact, no strongly-polynomial algorithm may exist due to a simple unconditional information-theoretic lower bound of \(n \log \Vert {\textbf{u}}-{\textbf{l}}\Vert _\infty \) , where \({\textbf{l}}, {\textbf{u}}\) are the vectors of lower and upper bounds. Our first result is that with parameters \({{\,\mathrm{\textrm{td}}\,}}_P(A)\) and \(\Vert A\Vert _\infty \) , this lower bound can be matched (up to dependency on the parameters). Second, with parameters \({{\,\mathrm{\textrm{td}}\,}}_D(A)\) and \(\Vert A\Vert _\infty \) , the situation is more involved, and we design an algorithm with complexity \(g({{\,\mathrm{\textrm{td}}\,}}_D(A), \Vert A\Vert _\infty ) n \log n \log \Vert {\textbf{u}}-{\textbf{l}}\Vert _\infty \) where  \(g\) is some computable function. We conjecture that a stronger lower bound is possible in this regime, and our algorithm is in fact optimal. Our algorithms combine ideas from scaling, proximity, and sensitivity of integer programs, together with a new dynamic data structure allowing fast sparse updates.