线段树笔记

有这样一类问题,给定一个数列,让你求某段区间内和。如果对某个值或某段区间内的值进行修改后,如何快速的求和。如果线性执行更新操作或求和操作,无疑时间复杂度太大了。
那么借助分治的思想,在执行更新区间的操作时,把它转化为几段区间的更新,同样求和操作时,也通过维护分段区间的和来达到快速求区间和的问题。线段树就是利用二叉树这种数据结构,来维护区间信息的一种数据结构。

Read More

如何实现进程代码段的分页度量

之前通过读取/proc/pid/mem的方法读取某个进程的内存数据,mem内部是用copy_from_user实现的,是对虚拟地址进行的操作。但是在某一时刻,该进程的所有内存页不一定都已经被加载到内存。由于虚拟内存的存在,只有那页代码被访问到时(copy_from_user()会判断缺页的情况),才会产生缺页中断,将该页代码加载到内存。这种方式并不够理想,理想的方法是判断哪些数据页已加载到内存中,然后对其进行度量。

Read More